1.jpg

2.jpg

#include <iostream>
#include <vector>


using namespace std;

/* 二分法使用場(chǎng)景的提示信息：數(shù)組元素有序排列、數(shù)組中無(wú)重復(fù)元素 */

/* 區(qū)間不變量: 保證在while循環(huán)中每次邊界的處理都堅(jiān)持相同的區(qū)間定義,[left, right] 或者 [left, right)*/
class Solution {
public:
    /* 方法1 */ 

    /*
        分別處理如下四種情況:
            (1).目標(biāo)值在數(shù)組所有元素之前 [0, -1];
            (2).目標(biāo)值等于數(shù)組中某一個(gè)元素 return mid;
            (3).目標(biāo)值插入數(shù)組中的某個(gè)位置 [left, right], return right + 1;
            (4).目標(biāo)值在數(shù)組所有元素之后的情況 [left, right], return right + 1;
    */
    int searchInsert1(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;  // 定義target在左閉右閉的區(qū)間里，即：[left, right]
        while(left <= right) {
            int mid = left + (right - left) / 2;   // 防止數(shù)據(jù)溢出，因此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).目標(biāo)值在數(shù)組所有元素之前 [0, 0);
            (2).目標(biāo)值等于數(shù)組中某一個(gè)元素 return mid;
            (3).目標(biāo)值插入數(shù)組中的某個(gè)位置 [left, right), return right;
            (4).目標(biāo)值在數(shù)組所有元素之后的情況 [left, right), return right;
    */
    int searchInsert2(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size();  // 定義target在左閉右開(kāi)的區(qū)間里，即：[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;
    }

};