优选算法的折半之智：二分查找专题(二)
专栏：算法的魔法世界
个人主页：手握风云
目录
一、例题讲解
1.1. 山脉数组的峰顶索引
题目很简单，要求我们在数组中找出一个值，这个值要比它左右元素都大。利用折线表示如下图所示。
我们先想一个暴力解法：利用一个指针去遍历一遍数组，如果某个元素比它的下一个元素大，那么返回这个元素的下标。我们最坏情况下要遍历到倒数第二个元素，所以时间复杂度为
。
从上图中我们已经可以看出，数组已经被分成两段，左边是递增的，右边是递减的，符合“二段性”，可以利用二分查找。如果arr[mid] > arr[mid-1]，则left=mid（因为中间值可能就是我们要找的结果）；如果arr[mid] < arr[mid-1]，则right=mid-1。
完整代码实现：
class Solution { public int peakIndexInMountainArray(int[] arr) { int left = 1,right = arr.length - 2; while(left < right){ int mid = left + (right - left + 1)/2; if(arr[mid] > arr[mid - 1]) left = mid; else right = mid - 1; } return left; } }1.2. 寻找峰值
与上一题不同的是，这道题的数组元素是上升、下降不断交替的。或者是递增的，或者是递减的。
我们先来思考暴力解法：从第一个下标开始向后遍历，然后分情况讨论（如下图三种情况）。最坏情况下可能要走到最后一个元素，所以时间复杂度为
。
如果走到了数组的某个位置i，此时的nums[i] > nums[i+1]，那么在i的左边的区间一定会存在一个峰值；相反，如果nums[i] < nums[i+1]，那么在i的右边的区间一定会存在一个峰值。这样就会把数组分成了两个部分，取其中一个区间去查找，那么我们就可以用二分查找进行优化。
完整代码实现：
class Solution { public int findPeakElement(int[] nums) { int left = 0, right = nums.length - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < nums[mid + 1]) left = mid + 1; else right = mid; } return left; } }1.3. 寻找旋转排序数组中的最小值
题目有点长，我们首先需要理解旋转的定义。每旋转一次，将数组中最大的元素移动至最前面（如下图所示）。
暴力解法：从头到尾遍历一边数组，比较出里面的最小值，时间复杂度为
。
通过上面的示例1，我们可以很明显地发现“二段性”，左边是严格大于某个值的递增区间，右边是严格小于某个值递增区间，并且数组中没有重复元素，折线表示如下图所示。，我们以D点为参照物，“二段性”体现在AB区间是nums[i] > nums[i-1]，CD区间是nums[i] < nums[i-1]。
完整代码实现：
class Solution { public int findMin(int[] nums) { int left = 0, right = nums.length - 1; int x = nums[right];// 标记最后一个元素 while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > x) left = mid + 1; else right = mid; } return nums[left]; } }1.4. 点名
题目解析：在一个升序数组中找到唯一一个缺失的数字并返回这个数字。
这道题可以有多种解法。1.哈希表：创建一个长度为n-1的哈希表，将数组元素放入，空出的位置就是丢失的数字。2.直接遍历数组，找出某个位置断掉的元素。3.位运算。利用0——n-1与数组里的元素进行按位异或操作，相同的数字就可以消去，最后剩下的数字就是缺失的数字。但这几种算法的时间复杂度都为
。
我们观察一下下图数组元素与下标的关系。在缺失的数字之前，数组元素与数组下标是一一对应的，到缺失的位置时，缺失的数字比数组元素小1。
我们注意一个细节：如果给定的数组为[0,1,2,3]，数组元素与下标都是一一对应的，而缺失的数字为最后一个元素加一。所以最后返回的时候，我们需要判断一下返回值的数组下标与数组元素是否相等。
完整代码实现：
public class Solution { public int takeAttendance(int[] records) { int left = 0, right = records.length - 1; while (left < right) { int mid = left + (right - left) / 2; if (records[mid] == mid) left = mid + 1; else right = mid; } return records[left] == left ? left + 1 : left; } }
