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;

     }