二分查找

二分查找总结，模板和相关题

参考邓俊辉老师的《数据结构》56页

1. 返回第一个大于target值的索引

//始终满足[0, lo) <= target, [hi, n) > target
public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int lo = 0, hi = n;
        while(lo < hi){
            int mi = (lo + hi) / 2;
            if(nums[mi] <= target){
                lo = mi + 1;
            }else{
                hi = mi;
            }
        }
    	//最后lo == hi, 返回第一个大于target的索引，返回lo--为插入位置
        return lo;
    }

Copy

1. 返回第一大于等于target值的索引

//始终满足[0, lo) < target, [hi, n) >= target
public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int lo = 0, hi = n;
        while(lo < hi){
            int mi = (lo + hi) / 2;
            if(nums[mi] < target){
                lo = mi + 1;
            }else{
                hi = mi;
            }
        }
    	//最后lo == hi, 返回第一大于等于target的索引
        return lo;
    }

Copy

这两种情况应该够用了。右边界取n还是n-1看具体情况，返回第一个大于或大于等于的，下标可能在n（即所有数都比target小），[lo,hi]是所求的下标范围，能取到n那hi就定到n。

有时候mi需要向上取整，这就不记了

相关题：

• 540，记住
• 153，比较mi和hi