Largest Smaller Position Target

Binary Search

Problem

find the largest smaller position of target

example:

1 2 3 3 3 3 3 4 5 6 for here, left is what we want l r

3 3 3 3 3 4 5 6 for here, there is no smaller target, return -1 l r

Solution

left will be the target, left - 1 will be the largest smaller.

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