/*
Binary Search:
Assumes that @arg array is sorted increasingly
return Return i such that |array[i] - target| is smallest among all i and -1 for an empty array.
Returns the smallest i for multiple candidates.
435563
function (target, array) {
    if (array.length === 0) {
      return -1
    }
    var index = this.findLowerBound(target, array)
    if (index < 0) {
      return 0
    } else if (index >= array.length - 1) {
      return array.length - 1
    } else {
      var middle = (array[index] + array[index + 1]) / 2
      return target <= middle ? index : index + 1
    }
  }
712659
def discrete_binary_search(tab, lo, hi):
    
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if tab[mid]:
            hi = mid
        else:
            lo = mid + 1
    return lo
688342
private static int binarySearch(int[] arr, int value) {
		int found = 0;
		int left = 0;
		int right = arr.length - 1;
		while (left < right) {
			if (right - left == 1) {
				found = value < arr[left] ? left : right;
				break;
			}

			int middle = left + (right - left) / 2;
			if (value < arr[middle]) {
				right = middle;
			} else {
				left = middle;
			}
		}
		return found;
	}
196560
function binarySearchIndices( value ) {

			function binarySearch( start, end ) {

				// return closest larger index
				// if exact number is not found

				if ( end < start )
					return start;

				var mid = start + Math.floor( ( end - start ) / 2 );

				if ( cumulativeAreas[ mid ] > value ) {

					return binarySearch( start, mid - 1 );

				} else if ( cumulativeAreas[ mid ] < value ) {

					return binarySearch( mid + 1, end );

				} else {

					return mid;

				}

			}

			var result = binarySearch( 0, cumulativeAreas.length - 1 )
			return result;

		}
671372
private int findMin(Comparator comparator, int index, int len)
  {
    if (index >= heapSize) {
      return -1;
    }
    int limit = Math.min(index, heapSize - len) + len;
    int minIndex = index;
    for (int i = index + 1; i < limit; i++) {
      if (comparator.compare(buf.getInt(i * Integer.BYTES), buf.getInt(minIndex * Integer.BYTES)) < 0) {
        minIndex = i;
      }
    }
    return minIndex;
  }
875142
function find( array, condition ) {

    const index = findIndex( array, condition );

    return index < 0 ? void 0 : array[ index ];

}
391862
private int binarySlotSearch() {

        int low     = 0;
        int high    = count;
        int mid     = 0;
        int compare = 0;

        while (low < high) {
            mid     = (low + high) / 2;
            compare = compare(mid);

            if (compare <= 0) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }

        return low;
    }
672535
@Private static int binarySearch(IntList ascendingInts, int value) {
    for (int begin = 0, to = ascendingInts.size();;) {
      if (begin == to) return begin;
      int i = (begin + to) / 2;
      int x = ascendingInts.get(i);
      if (x == value) return i;
      else if (x > value) to = i;
      else begin = i + 1;
    }
  }
1089098
private int binarySearch(List<SparseItemset> candidates, SparseItemset scratch, int begin, int end) {
    --end;
    while(begin < end) {
      final int mid = (begin + end) >>> 1;
      SparseItemset midVal = candidates.get(mid);
      int cmp = midVal.compareTo(scratch);

      if(cmp < 0) {
        begin = mid + 1;
      }
      else if(cmp > 0) {
        end = mid - 1;
      }
      else {
        return mid; // key found
      }
    }
    return -(begin + 1); // key not found, return next
  }
966992
private int binaryGreaterSearch() {

        int low     = 0;
        int high    = count;
        int mid     = 0;
        int compare = 0;

        while (low < high) {
            mid     = (low + high) / 2;
            compare = compare(mid);

            if (compare < 0) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }

        return low == count ? -1
                            : low;
    }
174936
private int compare(int i) {

        if (sortOnValues) {
            if (targetSearchValue > values[i]) {
                return 1;
            } else if (targetSearchValue < values[i]) {
                return -1;
            }
        } else {
            if (targetSearchValue > keys[i]) {
                return 1;
            } else if (targetSearchValue < keys[i]) {
                return -1;
            }
        }

        return 0;
    }
1299462
def searchsorted(arr, N, x):
    
    L = 0
    R = N-1
    done = False
    m = (L+R)//2
    while not done:
        if arr[m] < x:
            L = m + 1
        elif arr[m] > x:
            R = m - 1
        elif arr[m] == x:
            done = True
        m = (L+R)//2
        if L>R:
            done = True
    return L
1147584
public static int searchDescending(short[] shortArray, short value) { 
        int start = 0;
        int end = shortArray.length - 1;
        int middle = 0;
        
        while(start <= end) {
            middle = (start + end) >> 1;
        
            if(value == shortArray[middle]) {
                return middle;
            }
            
            if(value > shortArray[middle]) {
                end = middle - 1 ;
            }
            else {
                start = middle + 1;
            }
        }
                

        return -1;
    }
1190912
protected int binarySearch(int value) {
		int left = 0;
		int right = size-1;
		while(left <= right) {
			int mid = (left + right)>>1;
			int midValue = elementData[mid];
			if(value==midValue) return mid;
			if(value<midValue) right = mid-1;
			else left = mid+1;
		}
		return -(left+1);
	}
731843
function(ary, item, i, l) {
        if (ary.indexOf) return ary.indexOf(item)
        for (i = 0, l = ary.length; i < l; i++) if (ary[i] === item) return i
        return -1
    }
1139058
function binarySearch(arr, item, comparator) {
  var low = 0;
  var high = arr.length;
  var mid;
  while (low < high) {
    mid = (low + high) >>> 1;
    if (comparator(arr[mid], item) < 0) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }
  return low;
}
783037
private static int unsignedBinarySearch(int[] a, int fromIndex, int toIndex, int key,
      Comparator<? super Integer> c) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
      int mid = (low + high) >>> 1;
      int midVal = a[mid];
      int cmp = c.compare(midVal, key);
      if (cmp < 0) {
        low = mid + 1;
      } else if (cmp > 0) {
        high = mid - 1;
      } else {
        return mid; // key found
      }
    }
    return -(low + 1); // key not found.
  }