leetcode筆記：Search Insert Position

一. 題目描述

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.

[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

二. 題目分析

題目的大意是，給定一個已排序的數組和一個目標值target，如果在數組中找到該目標值，就返回這個目標值的元素下標。如果沒有找到，就返回target應該插入到該數組中的位置下標。這個過程中，假設該數組中沒有重復元素。

和Search for a Range 的解法類似，二分查找即可，可能出問題的地方是對邊界條件的處理。

三. 示例代碼

#include 
#include 

using namespace std;

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

解題結果：

四. 小結

二分查找的經典題目，對邊界的情況需要額外考慮。該題實際上是實現：std::lower_bound() 的功能。