[Leetcode 35]Search Insert Position

Description:

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: 4

Example 4:

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

Example 5:

Input: nums = [1], target = 0
Output: 0

Constraints:

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

C code solution:

int searchInsert(int* nums, int numsSize, int target){
    unsigned int lo = 0;
    unsigned int hi = numsSize - 1;
    unsigned int mid;
    while(lo < hi){
        mid = (lo + hi) >> 1; // (lo+hi)/2
        if(nums[mid] == target)
            return mid;
        if(nums[mid] < target){
            lo = mid + 1;
        }else{
            hi = mid;
        }
    }
    // when lo == hi
    if(nums[lo] < target)
        return lo + 1;
    else
        return lo;
}

Explanation:

使用Binary Search。設lo, hi來界定每round的範圍，每round檢查mid位置的值是否等於target。若是直接return。若否且小於，代表target可能在右邊，所以將lo = mid + 1，若為大於，代表target可能在左邊，所以將hi = mid。直到最後兩側移動到一起(代表沒在array中找到target)，即lo == hi，在檢查這個位置的值比target大還小，以決定target該擺的位置。