二分查找

二分查找 是一种常用的查找算法，适用于数组规模较大且有序的序列，时间复杂度是O(LogN)。

算法的主要思路是：先从序列中间开始查找，如果目标小于中间数，则向前继续查找，如果目标大于中间数，则向后继续查找（升序的情况，降序相反）。

比如，目标值为4，数组是[1, 2, 3, 4, 6, 7, 9, 12, 18]，二分查找过程如下

二分查找算法Java实现如下

拓展思考

二分查找的一些简单变种，需要我们对查找的条件进行适当调整。

1. 给定一个有序的数组，查找第一个等于 value 的下标，找不到返回 -1。
2. 给定一个有序的数组，查找第一个大于等于 value 的下标，都比 value 小则返回 -1。

寻找峰值

峰值元素是指其值大于左右相邻值的元素。

给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设nums[-1] = nums[n] = -∞ 。

示例 1：

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

示例 2：

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5 
解释：你的函数可以返回索引 1，其峰值元素为 2；或者返回索引 5， 其峰值元素为 6。

提示：

• 1 <= nums.length <= 1000
• -2^31 <= nums[i] <= 2^31 - 1
• 对于所有有效的 i 都有 nums[i] != nums[i + 1]

进阶：你可以实现时间复杂度为 O(logN) 的解决方案吗？

很容易想到的一个思路就是遍历数组，只要找到第一个满足nums[i-1]<nums[i]>nums[i+1]的元素，由于上面有假设nums[-1] = nums[n] = -∞，其实只要我们从数组第一个元素nums[0]（大于nums[-1]）开始，找到第一个满足nums[i]>nums[i+1]的元素即可，没有的话就返回数组最后一个元素nums[nums.length-1]（大于nums[n]）。

更加高效的一个思路是二分查找，在常规的二分查找算法中，一般要求数组完全有序，但是这道题给的数组并非完全有序，我们可以对二分查找的条件进行修改。

首先我们从中间mid开始，对比nums[mid]和nums[mid+1]，因为题目说明不会有nums[i] != nums[i + 1]，所以结果有以下两种情况。

1. nums[mid] > nums[mid+1]，说明肯定存在一个峰值是mid或者在mid左边，所以继续在数组左边查找。
2. nums[mid] < nums[mid+1]，说明肯定存在一个峰值是mid+1或者在mid+1右边，所以继续在数组右边查找。

无论哪种情况，我们都是一直往某个峰值方向找，所以当 left == right，就找到了其中一个峰值。