題目： LeetCode - 35. Search Insert Position

題目說明

給一個由小至大排序的陣列，及一個 target，求 target 應該插入到的位置 ( index )。

解題思路

由於是排序過的陣列，所以使用二分法查詢即可。 ( 可直接使用 lower_bound() 完成二分法 )

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int searchInsert(vector<int>& nums, int target)
    {
        return binarySearch(nums, target);
        //return lower_bound(begin(nums), end(nums), target) - begin(nums);
    }
    
private:
    int binarySearch(vector<int>& nums, int target)
    {
        int l = 0, r = nums.size();
        while (l < r)
        {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) return mid;
            if (target > nums[mid]) l = mid + 1;
            else r = mid;
        }
        return r;
    }
};