看到一个总结网址，还没来得及看完。
https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/

牛客剑指offer中一道题，二维数组中的查找
leetcode第35题Search Insert Position

文章的总结两个思路
思路1 while(left <= right)
思路2 while(left < right) 是排除，在left=right时终止，最后剩下一个元素，可能就是答案。「左右边界向中间走，两边夹」本文主要讨论思路2

1
2
3
4
while (left < right) {
    用本轮区间即leftright值算mid;
    比较mid和target确定下轮区间即leftright值；
}

举例如下 最普通二分-找到一个等于target的值就行

1
2
3
4
5
6
7
8
9
10
11
12
13
while (left < right) {
    int mid = left + (right - left) / 2;
    // 严格小于 target 的元素一定不是解
    if (nums[mid] < target) {
        // 下一轮搜索区间是 [mid + 1, right]
        left = mid + 1;
    } else {
        // 下一轮搜索区间是 [left, mid]
        right = mid;
    }
}

可能找到最后也没找到，后面可能要加补丁。下面有详细介绍。

因为35题可以理解为找到大于等于 target 的第 11 个元素的位置，所以严格小于 target 的元素一定不是解。上面是把 (left,mid) 排除出去了所以剩下的区间就是 (mid+1,right) .


关于取中位数
基于此题解，有个记忆的口诀是「左动取左，右动取右」，即 if (…) left = mid + 1; 归为「左动」，对应左中位数；if (…) right = mid - 1; 归为「右动」，对应右中位数。 详见这个里面https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/
评论区里lzhlyle的回答。

1
2
3
4
5
6
7
8
9
10
11
//找到第一个出现的target
while(left<right)
    {
        mid=left+(right-left)/2;//左中点
        if(nums[mid]<target)
             left=mid+1;
        else if(nums[mid]>target)
            right=mid-1;//此处两个right可以合并成right=mid 但我觉得不好理解 没有合并
        else
            right=mid;
    }
1
2
3
4
5
6
7
8
9
10
11
// 查找最后一个值等于给定值的元素
  while(left<right)//找到最后一个出现的target 此时必须上取整 右中点
    {
        mid=left+((right-left+1)>>1);//上取整 右中点
        if(nums[mid]<target)
            left=mid+1;//此处两个left可以合并
        else if(nums[mid]>target)
            right=mid-1;         
        else
            left=mid;//此处不一样          
    }

以下把等于改成大等或小等 只需要改补丁的if就行了

1
2
3
4
5
6
7
8
9
10
11
// 查找第一个大于等于给定值的元素
private int firstLargeOrEquals(int[] arr, int target) {
    int l = 0, r = arr.length - 1;
    while (l < r) {
        int mid = l + ((r - l) >> 1);
        if (arr[mid] < target) l = mid + 1;
        else r = mid; // 收缩右边界不影响 first equals
    }
    if (arr[l] >= target && (l == 0 || arr[l - 1] < target)) return l; // >=
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12

// 查找最后一个小于等于给定值的元素
private int lastLessOrEquals(int[] arr, int target) {
    int l = 0, r = arr.length - 1;
    while (l < r) {
        int mid = l + ((r - l + 1) >> 1);
        if (arr[mid] > target) r = mid - 1;
        else l = mid; // 收缩左边界不影响 last equals
    }
    if (arr[l] <= target && (l == arr.length - 1 || arr[l + 1] > target)) return l; // <=
    return -1;
}

---

对于704题最普通的二分查找来说标准答案给的是 

1
2
3
4
5
6
7
while(left <= right) {
    ···
        left = mid + 1; 
    ···
        right = mid - 1;
    ···
}

搜索区间为空的时候应该终止。

如果硬要用while(left < right) 也可以但在结束后得加上一个补丁。
循环只剩一个数时候会终止，此时left=right。得判断一下他是不是target。

1
2
3
4
5
6
7
8
9
while(left <= right) {
    ···
        left = mid + 1; 
    ···
        right = mid - 1;
    ···
}
if (nums[left]==target)
        return left;

https://leetcode-cn.com/problems/find-in-mountain-array/ 山脉这道题里判断mid处单调性为什么要mid和mid+1比；而不用mid和mid-1比？可能是因为前者需要

1
2
left=mid+1;
right=mid;

而后者要 

1
2
left=mid;
right=mid-1;

我不确定这里说的对不对，但是前面提到过左中点要左动，也就是前者。后者会死循环。