This is the binary search algorithm that returns the position at which an element is found or the position it should be inserted at.

BinarySearchEqualOrLarger.java

/*
  This is the binary search algorithm that returns the position at which an 
  element is found or the position it should be inserted at if the element is not present.
  
  In other words this algorithm returns position (non conforming in case of duplicates) or the position
  of largest element than the one we were searching for if position not found.
*/

class BinarySearch {
    private static int search(int[] array, int val) {
        int left = 0, right = array.length - 1, middle;
        while (left <= right) {
            middle = left + (right - left) / 2;
            if (array[middle] == val) return middle;
            else if (array[middle] > val) right = middle - 1;
            else left = middle + 1; 
        }
      
        return left;
    }
}