First Element Not Smaller Than Target - Binary Search / Sorted Array

Problems
24

If you enter a target number greater than the max number in the list, “-1” should indeed be returned as we are to only return the first index that is up to or greater than the target number. However, there is an assumption that the list would always contain a number that is greater or equal to the target number.

25

Instead of using boundary_index, it seems simpler to me to just peak over one element to the left to see if you can return early. Also could save some iterations if you happen to land on the boundary earlier on.

function firstNotSmaller(arr, target) {
let start = 0;
let end = arr.length - 1;

while (start <= end) {
    const mid = Math.floor((end - start) / 2) + start;
    
    if (arr[mid] >= target) {
        if (mid === 0 || arr[mid-1] < target) return mid;
        
        end = mid - 1;
    } else {
        start = mid + 1;
    }
}


return -1;

}

26

i believe it makes sense to return early if target is found?

function firstNotSmaller(arr, target) {
let [l, r] = [0, arr.length - 1];
let result;

while (l <= r) {
   const m = Math.floor((l + r) / 2); 
   if (arr[m] < target)
       l = m + 1; 
   else if (arr[m] > target) {
       result = m; 
       r = m - 1; 
   }
   else 
       return m; 
}

return result;

}

27

Though what if the first occurrence of that element is before the one found? Consider a case such as 3 3 3 3 3 and target 3. You want to return 0 in that case and not 2.

28

I really like the answer simple and nromal this is my answer:

public static int firstNotSmaller(List<Integer> arr, int target) {
    int start=0;
    int end=arr.size()-1;
    while (start<=end)
    {
        //avoiding stack overfllow
        int midle=end + (start-end )/2;
        //posible solution
        if(target<=arr.get(midle))
        {
            // we found our answer
            if(midle>0 && target>arr.get(midle-1))
            {
                return midle;
            }// there is bigger numbers than our target
            else if(midle>0 && arr.get(midle-1)>=target)
            {
                // we need to shirkn our end
                end=midle-1;
            }
            //corner case
            else if(midle==0)
            {
                return midle;
            }
        }// we need to shirnk our search
        else if(target>arr.get(midle))
        {
            start=midle+1;
        }
    }
    return -1;
}
29

I had the same idea as well, it seems like a simpler approach. My solution was:

function firstNotSmaller(arr, target) {
if (arr[0] >= target) return 0

let left = 0;
let right = arr.length - 1;

while(left <= right) {
    let mid = Math.floor((left + right) / 2);
    
    if (arr[mid] >= target) {
        if (arr[mid - 1] < target) return mid
        right = mid - 1
    } else {
        left = mid + 1
    }
}

}