Binary Search 二分法方法总结

code教你做人：二分法核心思想是把一个大的问题拆成若干个小问题，最重要的是去掉一半或者选择一半。

二分法模板：

 public int BinarySearchTemplate(int[] nums,int target) {

         if(nums == null || nums.length == 0) return -1;

         int lo = 0;

         int hi = nums.length - 1;

         //A: lo < hi [1,2]找1 找last position会死循环

         //B: lo <= hi

         //C: lo + 1 < hi

         //lo  + 1 < hi 相邻就要退出循环，lo = 1，hi = 2

         while(lo + 1 < hi) {

             int mid = lo + (hi - lo) / 2;

             if(nums[mid] == target)

                 return mid;

             else if(nums[mid] < target) {

                 lo = mid;

                 //hi = mid - 1 also works，但是不+1/-1更好记

             }

             else {

                 hi = mid;

                 //lo = mid + 1 also works

             }

         }

         //lo + 1 < hi 方法需要在结尾判断lo和hi

         if(nums[hi] == target) return hi;

         if(nums[lo] == target) return lo;

         return -1;

     }

两种类型题：

1.有序数列找特定值

【1】找target的下标，可能有重复，返回任意符合条件的index，无则return -1。

【2】返回target第一次出现的下标，可能有重复，无则return -1。

【3】返回trage最后一次出现的下标，可能有重复，无则return -1。（出现死循环的可能性很高 = > lo + 1 < hi 代替）

2.OOOOOOOXXXXXXXXXX 找圈圈叉叉的分割线

【1】找最后一个O

【2】找第一个X

结论：

1.+1不会对结果造成影响，只需要在最后只剩两个数的时候进行判断即可。

2.二分法的目的不是为了找到答案，而是为了缩小区间，从有限的候选中找出答案。

秒客网

Binary Search 二分法方法总结

Binary Search 二分法方法总结

code教你做人：二分法核心思想是把一个大的问题拆成若干个小问题，最重要的是去掉一半或者选择一半。

二分法模板：

两种类型题：

1.有序数列找特定值

2.OOOOOOOXXXXXXXXXX 找圈圈叉叉的分割线

结论：

相关题目：

相关文章