本文最后更新于2021年07月9日 # 二分查找 二分查找是一种应用了分治思想的查找算法，*基本思想十分简单，只是对于一些特殊问题有一些小点需要注意*，将在后面例题中介绍。 ## 应用范围 在**顺序存储**的数据集中查找某个目标值 > 顺序存储可以是升序降序，一些特殊情况甚至可以是部分有序（比如即将介绍的旋转数组问题） ## 基本思想 此处以升序的数据集作为例子，将数据集中间位置的值与目标值进行比较，如果比目标值大则将尾指针移动至中间位置，对于头尾指针之间的数据继续进行二分查找；如果中间位置的值比目标值小则将头指针移动至数据集中间。时间复杂度可以做到$O(n) = log_2n$。 ## 例题：旋转数组问题 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。 示例 1： ``` 输入：[3,4,5,1,2] 输出：1 ``` 示例 2： ``` 输入：[2,2,2,0,1] 输出：0 ``` 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 ## 题解 这个数组即前面提到的“部分有序”，是升序 但又不完全是，由于需要查找的元素所处位置的特殊性而且以查找元素为分界线前后元素均有序，所以可以使用二分查找进行解题。 ### 上代码 ```java class Solution { public int minArray(int[] numbers) { int i,j,m; j = numbers.length-1; i = 0; m = (i+j)/2; while(i!=j){ if(numbers[m]<numbers[j]){ j = m; m = (i+j)/2; } else if(numbers[m]>numbers[j]){ i = m+1; m = (i+j)/2; } else if(numbers[m] == numbers[j]){ j = j-1; m = (i+j)/2; } } return numbers[i]; } } ``` ### 一个小点 这个题解前面大部分就是基本的二分查找，但是：在一些特殊情况下，如本题的 第16行处 遇到重复值的情况如何处理: 1. **当 x<jx < jx<j 时：** 易得执行 j=j−1j = j - 1j=j−1 后，旋转点 xxx 仍在区间 [i,j][i, j][i,j] 内。 2. **当 x=jx = jx=j 时：** 执行 j=j−1j = j - 1j=j−1 后越过（丢失）了旋转点 xxx ，但最终返回的元素值 nums[i]仍等于旋转点值 nums[x] 。
评论