題目描述

給定一個排序數(shù)組和一個目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會被按順序插入的位置。

你可以假設(shè)數(shù)組中無重復(fù)元素。

示例

示例 1:

輸入: [1,3,5,6], 5
輸出: 2
示例 2:

輸入: [1,3,5,6], 2
輸出: 1
示例 3:

輸入: [1,3,5,6], 7
輸出: 4
示例 4:

輸入: [1,3,5,6], 0
輸出: 0

題目分析

二分搜索應(yīng)用，需要注意搜索邊界的處理，即一開始如果令low=0,high=n-1,則二分搜索的區(qū)間是閉區(qū)間[0,n-1]，后面變換high或者low的值時也應(yīng)該一直保持搜索區(qū)間是完全閉合的狀態(tài)，即high=mid-1。如果令low=0,high=n,則二分搜索區(qū)間是[0,n)，左閉右開，后面變換high時，應(yīng)該令high=mid，一直保持左閉右開的搜索區(qū)間。

C++代碼

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int low = 0;
        int high = n-1;
        while(low <= high){
            int mid = low + (high-low)/2;
            if (target < nums[mid]){
                high = mid-1;
            }
            else if (target > nums[mid]){
                low = mid+1;
            }
            else{
                return mid;
            }
        }
        return low;
        
    }
};