Difficulty: Medium

【題目】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

翻譯

查找插入位置
難度系數(shù)：中等
給定一個(gè)有序數(shù)組和一個(gè)目標(biāo)值，如果找到目標(biāo)值則返回該索引。如果不能，返回按照順序它應(yīng)被插入位置的索引。

一些示例

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

// 二分檢索 時(shí)間復(fù)雜度log2(n)
- (int)searchInsertPosition:(NSArray<NSNumber *> *)sortedArray targetValue:(NSNumber *)target {
    
    if (sortedArray.count == 0) {
        
        return 0;
    }else {
        
        int left = 0;
        int right = (int)sortedArray.count - 1;
        
        while(left <= right) {
            
            int mid = (left+right)/2;
            
            if (sortedArray[mid] == target)
                
                return mid;
            else if (sortedArray[mid] > target)
                
                right = mid-1;
            else
                
                left = mid+1;
        }
        
        // left>right
        return left;
    }
}

之前學(xué)的C全就著饅頭進(jìn)肚子了。原諒我現(xiàn)階段只會用OC來寫，看起來不是很方便，最近在學(xué)Python，以后用Python寫吧