二分查找的一些常见问题以及习题

记录总结以下二分法以及常见的一些操作：

int binaryleft(vector& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (nums[middle] == target) {
                ...
            } else if (nums[middle] > target) {
                ...
            } else {
                ...
            }
        }
        return left;
    }

• 边界如何取？

对于 r 的取值，取 nums.length - 1 还是 nums.length 似乎是个很难抉择的问题，但是事实上来说，这两个值都是可以的，只不过这和 跳出循环 与 r 的移动 有着密切的关系，也常常是在这种地方陷入疯狂挠头的处境，也就是这种情况，感觉一定不是自己的问题，头发也日渐减少…

• 取值范围是什么？

我们的取值区间的两个端点都是闭区间，也就是 [ l, r ]，左闭右闭，l 和 r 的值都可以取得到

• l 能不能等于 r ？

这个时候如果出现 l = r 的情况是没有任何问题的，因为 [ r, r ] 是有意义的

• 什么时候退出循环？

闭区间 [ l, r ]，如果 l = r，这个时候是一个临界值，当 l > r 时，我们应该退出循环

• 关于 r = mid - 1

第一次的查询范围是**[ l, r]，判断mid之后，应该变为[ l, mid -1 ]或者[ mid + 1, r ]**，r总会指向需要进行判断的元素。我们当前判断的是mid，mid判断完成下一步要找的就是下一个要判断的区间。

1、 取值范围是什么？

这和前面得那种情况不一样，r得取值是 nums.length ，这个值我们是取不到的，所以这个时候区间是左闭右开得，也就是 [ l, r )

2、 l 能不能等于 r ？

这个时候如果出现 l = r 的情况，[ r, r ) ，既包含 r ，又不包含 r ，这个时候是没有意义的，所以 l 不能等于 r

3、 什么时候退出循环？

左闭右开区间 [ l, r )，如果 l = r，这个时候是没有意义的，这个时候的临界值是 l = r - 1，所以，当 l = r 时，我们应该退出循环

4、 关于 r = mid

第一次的查询范围是 [ l, r)，判断 mid 之后，应该变为 [ l, mid ) 或者 [ mid + 1, r ) ，关于为什么是 [ l, mid ) ，我们这个时候的 mid 位置的元素是不会访问的，r指向的是最后一个元素的后一个位置，其实 [ l, mid ) 就相当于 [ l, mid - 1 ]

思路：主要考察的其实是能不能明白二分查找的过程。其实也简单，就看二分查找停留的最后一个位置的左、中、右走向。又因为循环的终止点是left > right，刚好就是新序号要插入的位置。

   // 求target点的左边界点
	int binaryleft(vector& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (nums[middle] >= target) {
                right = middle - 1; // 在找到满足target点之后，还继续向左移动,此时最临界的移动点为刚好满足nums[middle] = target
            } else {
                left = middle + 1; // 
            }
        }
        return left;
    }

上面求的是目标点右边界点，至于说为什么会成立呢？我们在找到满足target点之后，还继续向左移动，此时right就是在检测左边是否还有出现满足target的点，如果还满足就继续向左走。直到当不满足左边等于target的时候，left指针会继续向右走，直到跳出循环，也就是left > right的时候跳出循环，此时找的边界点就是最左边的target的起始点。

  // 求target点的右边界点
	    int binaryright(vector& nums, int target) {
        int left = 0 ;
        int right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target){
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }

class Solution {
public:
    int search(vector& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right){
            int middle = left + (right - left) / 2;
            if (nums[middle] == target) {
                return  middle;
            }else if (nums[middle] > nums[right]) {    //如果middle位置 > right，则说明左边必然是有序的
                if (nums[left] <= target && nums[middle] > target ) {  //如果左边有序，并且中间值大于目标值，且最左边小于目标
                    right = middle - 1;								   //那么说明目标值只有可能出现在左边
                }else {
                    left = middle + 1;			//否则跳到右边继续去判断到底那一部分是有序哪一部分是无序
                }
            }else { //如果middle位置 < right，则说明右边必然是有序的
                if (nums[middle] < target && nums[right] >= target) { 
                    left = middle + 1 ;
                } else {
                    right = middle - 1;
                }
            }
        }
        return -1;
    }
};

上面的核心思路就是：

因为是有旋转的，所以就一定是一半有序，另外一半有序或者无序。并且在有序部分来判断是否有目标值，无序部分继续去寻找有序部分，不断循环下去。具体过程：我们可以根据中心位置和最右边的大小来判断他们是不是有序的。如果中心位置大于右边，则说明左边一定是有序的。如果中心位置小于右边，则说明右边一定是有序的。知道哪里有序之后，我们可以从有序的部分下手，看看我们的目标是否落在有序部分内。主要查看其左边界或者右边界来调整。例如知道左边是有序的，则如果中间位置大于目标和最左边小于目标，则说明我们的目标就在这个区间。否则就从另外一个区间继续去找有序部分。