二分查找
二分查找又叫折半查找，但是很容易写错，因为不好界定边界
首先看一道二分查找的题目
135. 搜索插入位置
2给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
3
4你可以假设数组中无重复元素。
5
6示例 1:
7
8输入: [1,3,5,6], 5
9输出: 2
10示例 2:
11
12输入: [1,3,5,6], 2
13输出: 1
14示例 3:
15
16输入: [1,3,5,6], 7
17输出: 4
18示例 4:
19
20输入: [1,3,5,6], 0
21输出: 0
分析
二分查找基础条件是建立在有序数组的基础上，本题就是有序数组，然后目标数字与数组中各个值进行比较，
- 目标值比第一位元素小
- 目标值比最后一位元素大
- 目标值介乎于前俩种情况之间
解法1 暴力
从第一位遍历与目标值比较，确定位置，此处只说明思路，时间复杂度 o(n)
解法2 二分查找
首先说明一下题目中说数组无重复数据，所以暂且不考虑重复情况，重复情况在文末进行说明
首先确定题中的不变量[left,right]，既[0,nums.length-1],左闭右闭区间
看一下我的写法
1 /**
2 * 二分法 首先确定不变量，既不变区间【0，nums.length -1】,左闭右闭区间
3 * @param nums
4 * @param target
5 * @return
6 */
7 public int searchInsert(int[] nums, int target) {
8 int left = 0;
9 int right = nums.length -1;
10 while(left <= right){
11 //避免溢出
12 int middle = left + ((right -left)/2);
13 if(nums[middle]<target){
14 left = middle + 1;
15 }else if(nums[middle]>target){
16 right = middle -1;
17 }else{
18 return middle;
19 }
20 }
21 return right+1;
22 }
小结
以上题目主要想说明二分前确定好区间，才能确定好边界条件
二分查找重复值问题
当我们遇到[1,2,2,2,2,2]或者[1,1,1,2]这种情况可能会出现死循环该如何解决。
其实这种情况只会出现在二分查找的第三个判断上，既
nums[middle] == target所以只需要对这块进行处理，既向左以及想有找到所有相同元素的下标，至于要取最左还是最右看你的需求，那么看一下代码
1else { //表示arr[mid] == val
2 /*思路分析
3 1.在找到mid索引值，不要马上返回
4 2.向mid索引值的左边扫描,将所有满足1000，的元素的下标， 加入到集合ArrayList
5 3.向mid索引值的右边扫描，将所有满足1000， 的元素的下标，加入到集合ArrayList
6 4.将ArrayList返回*/
7
8 //向mid左边扫描
9 int temp = mid - 1;
10 while (true) {
11 if (temp < 0 || arr[temp] != val)//没有找到就退出循环
12 break;
13 //执行到这里说明找到了,就把找到的元素添加到集合中,继续向左找
14 indexList.add(temp);
15 temp -= 1;
16 }
17 indexList.add(mid);//加入已经找到了的元素【arr[mid]==val】
18 //向mid右边扫描
19 temp = mid + 1;
20 while (true) {
21 if (temp > arr.length - 1 || arr[temp] != val)
22 break;
23 //执行到这里说明找到了,就把找到的元素添加到集合中,继续向右
24 indexList.add(temp);
25 temp += 1;
26 }
27 return indexList;
28 }
测试用例 ：int[] arr = {1, 2, 3, 5, 6, 6,6, 6, 7, 8, 9};
target = 6；
返回的 indexList 就是 [4,5,6,7]既为数组中为6的下标；
总结
二分查找
- 注意边界条件
- 注意为有序数组
- 注意数组是否有重复元素
确定以上问题之后二分问题就能迎刃而解了
