algorithm - 二分查找小于或等于查找值的最接近值

Question

我正在尝试编写一种算法来查找小于或等于排序数组中搜索值的最接近值的索引。在数组[10, 20, 30] 的示例中，以下搜索值应输出这些索引:

1. 搜索值:9，索引:-1
2. 搜索值:10，索引:0
3. 搜索值:28，索引:1
4. 搜索值:55555，索引:2

我想对对数运行时间使用二进制搜索。我有一个 C 风格的伪代码算法，但它有 3 个基本情况。能否将这 3 个基本案例浓缩为 1 个以获得更优雅的解决方案？

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

根据您的递归方法，我建议使用以下 c++ 片段来减少不同情况的数量:

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;
}

基本上它执行正常的二进制搜索。只是最后一个case的return语句不同，满足了额外的要求。

这是一个简短的测试程序:

#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;
}

输出如愿:

-1
 0
 1
 2