二分法总结

二分法貌似简单，实则很多细节，需要多加注意才能写对。

应用

1 在单调递增数组中确认是否有指定target

    public int binarySearch(int[] nums, int target)
    {
        int left = 0 ;
        int right = nums.length - 1;
        int mid = 0;

        while(left <= right)
        {
            mid = left + ((right - left) >> 1);
            if (nums[mid] == target)
            {
                return mid;
            }
            else if (nums[mid] < target)
            {
                left = mid + 1 ;
            }
            else
            {
                right = mid - 1 ;
            }
        }
        return -1 ;
    }

2 在单调递增数组中查找第一个为target的值（每个值不唯一）

    public int binarySearchFirst(int[] nums , int target)
    {
        int left = 0 ;
        int right = nums.length - 1 ;
        int mid = 0 ;

        while(left < right)
        {
            mid = left + ((right - left) >> 1);
            if (nums[mid] < target)
            {
                left = mid + 1 ;
            }
            else
            {
                right = mid;
            }
        }

        if (nums[right] == target)
        {
            return left;
        }
        else
        {
            return -1 ;
        }
    }

3 在单调递增数组中查找最后一个为target的值（每个值不唯一）

    public int binarySearchLast(int[] nums , int target)
    {
        int left = 0 ;
        int right = nums.length  - 1 ;
        int mid = 0 ;

        while(left < right)
        {
            mid = left + ((right - left) >> 1) + 1;
            if (nums[mid] <= target)
            {
                left = mid;
            }
            else
            {
                right = mid - 1;
            }
        }
        if (nums[left] == target)
        {
            return left;
        }
        return -1 ;
    }

当然，还有如下变种

4 查找单调数组中第一个大于target的值

    public int binarySearchFirstGreaterThan(int[] nums , int target)
    {
        int left = 0 ;
        int right = nums.length - 1;
        int mid = 0 ;

        while(left < right)
        {
            mid = left + ((right - left) >> 1);
            if (nums[mid] <= target)
            {
                left = mid + 1 ;
            }
            else
            {
                right = mid;
            }
        }

        if (nums[left] > target)
        {
            return nums[left];
        }
        else
        {
            return -1 ;
        }
    }

5 查找单调数组中最后一个小于target的值

    public int binarySearchLastSmallerThan(int[] nums , int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;

        while (left < right) {
            mid = left + ((right - left) >> 1) + 1;
            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }

        if (nums[right] < target) {
            return nums[right];
        }

        return -1;
    }

总结

二分法核心要点是每次循环一定需要让left或者 right有一个值发生变动，否则就会出现死循环，写出不正确的二分法。
所以个人做法一般如下：

• 确定锚点
  一般求第一个出现的值用left，最后一个值用right来锚住答案；针对锚点分支的条件一定要激进，需要确保每次进入分支一定要显示的+1或者-1来发生偏移。

• 确定 mid偏移

mid = left + ((right - left) >> 1) + 1; // 右偏移
mid = left + ((right - left) >> 1)  ; // 左偏移

如果用left作为锚点，则使用左偏移将right逐渐拉至left 处退出循环，反之亦然。该偏移点分支条件就是锚点分支的简单else，偏移特性使得其一定会发生偏移。这样就确保了每次循环可以必然发生一侧的偏移，防止两侧都不动进入死循环。

• 返回值检查
  最后在返回前需要检查答案是否满足条件，不满足返回-1等无效值。

后话

务必务必务必每次循环一定需要让left或者 right有一个值发生变动！！！
之前的例子中，二分法用来直观的搜索值，但是其在如下场景中也是很多见的：
在一个可以确定上下界的单调解空间中，二分加速处理速度。
个人认为二分法的核心就是在单调解空间中加速搜索target。