Binary search for the closest value less than or equal to the search value

Question

I'm trying to write an algorithm for finding the index of the closest value that is lesser than or equal to the search value in a sorted array. In the example of the array [10, 20, 30], the following search values should output these indexes:

1. searchValue: 9, index: -1
2. searchValue: 10, index: 0
3. searchValue: 28, index: 1
4. searchValue: 55555, index: 2

I want to use binary search for logarithmic runtime. I have an algorithm in C-esque psuedocode, but it has 3 base cases. Can these 3 base cases be condensed into 1 for a more elegant solution?

int function indexOfClosestLesser(array, searchValue, startIndex, endIndex) {
  if (startIndex == endIndex) {
    if (searchValue >= array[startIndex]) {
      return startIndex;
    } else {
      return -1;
    }
  }

  // In the simplistic case of searching for 2 in [0, 2], the midIndex
  // is always 0 due to int truncation. These checks are to avoid recursing
  // infinitely from index 0 to index 1. 
  if (startIndex == endIndex - 1) {
    if (searchValue >= array[endIndex]) {
      return endIndex;
    } else if (searchValue >= array[startIndex]) {
      return startIndex;
    } else {
      return -1;
    }
  }

  // In normal binary search, this would be the only base case
  if (startIndex < endIndex) {
    return -1;
  }

  int midIndex = endIndex / 2 + startIndex / 2;
  int midValue = array[midIndex];

  if (midValue > searchValue) {
    return indexOfClosestLesser(array, searchValue, startIndex, midIndex - 1);
  } else if (searchValue >= midValue) {
    // Unlike normal binary search, we don't start on midIndex + 1.
    // We're not sure whether the midValue can be excluded yet
    return indexOfClosestLesser(array, searchValue, midIndex, endIndex);
  }
}

Answer 1

Based on your recursive approach, I would suggest the following c++ snippet that reduces the number of different cases a bit:

int search(int *array, int start_idx, int end_idx, int search_val) {

   if( start_idx == end_idx )
      return array[start_idx] <= search_val ? start_idx : -1;

   int mid_idx = start_idx + (end_idx - start_idx) / 2;

   if( search_val < array[mid_idx] )
      return search( array, start_idx, mid_idx, search_val );

   int ret = search( array, mid_idx+1, end_idx, search_val );
   return ret == -1 ? mid_idx : ret;
}

Basically it performs a normal binary search. It only differs in the return statement of the last case to fulfill the additional requirement.

Here is a short test program:

#include <iostream>

int main( int argc, char **argv ) {

   int array[3] = { 10, 20, 30 };

   std::cout << search( array, 0, 2, 9 ) << std::endl;
   std::cout << search( array, 0, 2, 10 ) << std::endl;
   std::cout << search( array, 0, 2, 28 ) << std::endl;
   std::cout << search( array, 0, 2, 55555 ) << std::endl;

   return 0;
}

The output is as desired:

-1
 0
 1
 2

Answer 2

Frankly speaking, I find the logic of finding a number greater than a given number a lot easier than the logic needed to find numbers less than or equal to a given number. Obviously, the reason behind that is the extra logic (that forms the edge cases) required to handle the duplicate numbers (of given num) present in the array.

public int justGreater(int[] arr, int val, int s, int e){
    // Returns the index of first element greater than val. 
    // If no such value is present, returns the size of the array.
    if (s >= e){
        return arr[s] <= N ? s+1 : s;
    }
    int mid = (s + e) >> 1;
    if (arr[mid] < val) return justGreater(arr, val, mid+1, e);
    return justGreater(arr, val, s, mid);
} 

and then to find the index of the closest value that is lesser than or equal to the search value in a sorted array, just subtract the returned value by 1:

ans = justGreater(arr, val, 0, arr.length-1) - 1;