L35 search insertion position

smallest larger position. Binary Search

Problem:

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.

• smallest larger position

• if target in the array, insert it directly to that's position

Example:

Input: [1,3,5,6], 5

output: 2

Solution:

when left <= right, if jump out of the while loop, left and right are adjacent, [left] will be the right of [right], since we want smallest larger, it will be left.

public int insert(int[] arr, int target){
    if(arr == null || arr.length == 0) return 0;
    int left = 0, right = arr.length - 1;
    if(target < arr[left]) return left;
    if(target > arr[right]) return right + 1;
    while(left <= right){
        int mid = left + (right - left)/2;
        if(arr[mid] >= target) right = mid -1;
        else left = mid + 1;
    }
    return left;
}