二分查找
学习数据结构与算法
二分查找 是一种常用的查找算法，适用于数组规模较大且有序的序列，时间复杂度是O(LogN)。
算法的主要思路是：先从序列中间开始查找，如果目标小于中间数，则向前继续查找，如果目标大于中间数，则向后继续查找（升序的情况，降序相反）。
比如，目标值为4，数组是[1, 2, 3, 4, 6, 7, 9, 12, 18]，二分查找过程如下
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 9
- 12
- 18
二分查找算法Java实现如下
1public class Main {
2
3 public static void main(String[] args){
4 int position = binarySearch(4, new int[]{1, 2, 3, 4, 5, 6, 7, 9, 12, 18});
5 System.out.println(position);
6 }
7
8 public static int binarySearch(int target, int[] array) {
9 int mid, left = 0, right = array.length - 1;
10 while (left <= right) {
11 mid = (left + right) / 2;
12 if (target > array[mid]) {
13 left = mid + 1;
14 } else if (target < array[mid]) {
15 right = mid - 1;
16 } else {
17 return mid;
18 }
19 }
20 return -1;
21 }
22}拓展思考
二分查找的一些简单变种，需要我们对查找的条件进行适当调整。
- 给定一个有序的数组，查找第一个等于 value 的下标，找不到返回 -1。
- 给定一个有序的数组，查找第一个大于等于 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]，所以结果有以下两种情况。
- nums[mid] > nums[mid+1]，说明肯定存在一个峰值是mid或者在mid左边，所以继续在数组左边查找。
- nums[mid] < nums[mid+1]，说明肯定存在一个峰值是mid+1或者在mid+1右边，所以继续在数组右边查找。
无论哪种情况，我们都是一直往某个峰值方向找，所以当 left == right，就找到了其中一个峰值。