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

<解題>

1. 用前後兩指標去縮減範圍，一次從砍半中間開始找，不過這題如果沒有找到的話，要把他插入，所以最後可以直接返回start值

class Solution {
        public int searchInsert(int[] A, int target) {
        int start = 0, end = A.length-1, mid = (start+end)/2;
        while(start<=end){
            if(A[mid]==target) return mid;
            if(A[mid]>target){
                end = mid-1;
            } else {
                start = mid+1;
            }
            mid = (start+end)/2;
        }
        return start;
    }
}

Time: O(log n) Space: O(1)

可以和704. Binary Search做比較