Search Insert Position（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

【题意】

    输出一个元素在一个已排序的数组中的位置，如果不存在输出它应该插入的位置

【分析】

    二分查找，如果找到就输出位置，找不到就输出它应该插入的位置

    复杂度：时间O(log n)，空间O(1)

【实现】

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