tsanmmmm2000's Tech Blog

Question

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

Thinking

此題可以實作二分搜尋法(Binary Search)來解。其概念是在一個有序的結構中，取中間值做為比較依據，若想尋找的目標(target)小於中間值，則取中間值的左半區繼續搜尋，反之則取右半區，我們不斷重複搜尋，直到target等於中間值即代表成功，若所有區域搜尋完仍不相等即代表失敗。此方法的時間複雜度為O(log n)，而搜尋過程也可以用一棵二元樹來表示

My C# Solution

public class Solution {
    public int SearchInsert(int[] nums, int target) {
        var low = 0;
        var high = nums.Length - 1;
        int mid;
        while(low <= high)
        {
            mid = (low + high) / 2;
            if (target < nums[mid])
            {
                high = mid - 1;
            }
            else if (target > nums[mid])
            {
                low = mid + 1;
            }
            else
            {
                return mid;
            }
        }
        return low;
    }
}