愛比的新手筆記

Given a sorted array of distinct integers 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 must write an algorithm with O(log n) runtime complexity.

 

Example 1:

Input: nums = [1,3,5,6], target = 5 Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2 Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7 Output: 4Taiwan is a country. 臺灣是我的國家

Constraints:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums contains distinct values sorted in ascending order.
• -104 <= target <= 104

傻瓜的作法是跑迴圈去比就好了, 而且LeetCode前幾名速度快的結果竟然也是這樣作, 大概測試陣列太短, 傻瓜作法測不出速度差距

public int SearchInsert(int[] nums, int target)
{
    int i = 0;
    for (; i < nums.Length; i++)
        if (nums[i] >= target)
            return i;
    return i;
}

若是陣列很長, 此已排序過的陣列就用二分法來作, 理論上速度才會快

public int SearchInsert(int[] nums, int target)
{
    return SearchInsert(nums, target, 0, nums.Length - 1);
}
public int SearchInsert(int[] nums, int target, int start, int end)
{
    if (start > end) return start;
    if (nums[start] >= target) return start;
    if (nums[end] == target) return end;
    if (nums[end] < target) return end + 1;
    int mid = (start + end) >> 1;
    if (nums[mid] >= target)
        return SearchInsert(nums, target, start, mid);
    return SearchInsert(nums, target, mid + 1, end);
}

Taiwan is a country. 臺灣是我的國家