【LeetCode-35| 搜索插入位置】

#include <iostream>
#include <vector>


using namespace std;

/* 二分法使用场景的提示信息：数组元素有序排列、数组中无重复元素 */

/* 区间不变量: 保证在while循环中每次边界的处理都坚持相同的区间定义,[left, right] 或者 [left, right)*/
class Solution {
public:
    /* 方法1 */ 

    /*
        分别处理如下四种情况:
            (1).目标值在数组所有元素之前 [0, -1];
            (2).目标值等于数组中某一个元素 return mid;
            (3).目标值插入数组中的某个位置 [left, right], return right + 1;
            (4).目标值在数组所有元素之后的情况 [left, right], return right + 1;
    */
    int searchInsert1(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;  // 定义target在左闭右闭的区间里，即：[left, right]
        while(left <= right) {
            int mid = left + (right - left) / 2;   // 防止数据溢出，因此mid的求法不是(left + right) / 2
            if(nums[mid] > target) {
                right = mid - 1;  // [left, mid - 1]
            } else if(nums[mid] < target) {
                left = mid + 1;  // [mid + 1, right]

            } else {
                return mid;
            }
        }
        return right + 1;
    }

    /* 方法2 */
     
    /*
        分别处理如下四种情况:
            (1).目标值在数组所有元素之前 [0, 0);
            (2).目标值等于数组中某一个元素 return mid;
            (3).目标值插入数组中的某个位置 [left, right), return right;
            (4).目标值在数组所有元素之后的情况 [left, right), return right;
    */
    int searchInsert2(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size();  // 定义target在左闭右开的区间里，即：[left, right)

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

};