C Upper and Lower Bound Implementations

upper_lower_bound.c

/*
Upper and lower bounds.
Upper bound: First where target < array[i]
Lower bound: First where !(array[i] < target)
Assume a 3 way comparision returns this.
[-1 -1 -1 -1  0  0  0  0  0  1  1  1  1  1]
              ^ Lower bound. ^
                             Upper bound.
*/

// Upper bound
int hi = array_size;
int lo = 0;
while (hi > lo) {
  const int mid = lo + (hi-lo)/2;
  if (target < array[mid]) {
    hi = mid;
  } else {
    lo = mid + 1;
  }
}
const int upper_bound = lo;


// Lower bound.
int hi = array_size;
int lo = 0;
while (hi > lo) {
  const int mid = lo + (hi-lo)/2;
  if (array[mid] < target) {
    lo = mid + 1;
  } else {
    hi = mid;
  }
}
const int lower_bound = lo;

Good for leetcode problems.