LeetCode—— 35 搜尋插入位置

問題描述

給定一個排序數組和一個目标值，在數組中找到目标值，并傳回其索引。如果目标值不存在于數組中，傳回它将會被按順序插入的位置。

你可以假設數組中無重複元素。

示例 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
           

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/search-insert-position

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

執行結果

代碼描述

思路：二分查找，如果查找不到，就退出循環，此時left== right, 額外判斷一下，nums[left] 與target 的大小關系，然後在傳回結果。

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