magic-index-lcci

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

本书是原谷歌资深面试官的经验之作，帮助了许多想要加入脸书、苹果、谷歌等 IT 名企的求职者拿到 Dream offer。本专题的 100+ 编程面试题是在原书基础上精心挑选出来的，帮助你轻松应战 IT 名企技术面试。

英文版：Cracking the Coding Interview，源自硅谷程序员的面试红宝书

LCCI

A magic index in an array <code>A[0...n-1]</code> is defined to be an index such that <code>A[i] = i</code>. Given a sorted array of&nbsp;integers, write a method to find a magic index, if one exists, in array A. If not, return -1. If there are more than one magic index, return the smallest one.

Example1:

<pre>
 Input: nums = [0, 2, 3, 4, 5]
 Output: 0
</pre>

Example2:

<pre>
 Input: nums = [1, 1, 1]
 Output: 1
</pre>

Note:

<ol>
	<li><code>1 &lt;= nums.length &lt;= 1000000</code></li>
	<li>This problem is the&nbsp;follow-up of the original problem in the book, i.e.&nbsp;the values are&nbsp;not distinct.</li>
</ol>

findMagicIndex

Magic Index LCCI

Array

Binary Search

魔术索引。 在数组<code>A[0...n-1]</code>中，有所谓的魔术索引，满足条件<code>A[i] = i</code>。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。

示例 1：

<pre>
 输入：nums = [0, 2, 3, 4, 5]
 输出：0
 说明：0下标的元素为0
</pre>

示例 2：

<pre>
 输入：nums = [1, 1, 1]
 输出：1
</pre>

说明：

<ol>
	<li>nums长度在[1, 1000000]之间</li>
	<li>此题为原书中的 Follow-up，即数组中可能包含重复元素的版本</li>
</ol>