二进制搜索小于或等于搜索值的最接近值

Question

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

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

我想使用二进制搜索进行对数运行时.我有一个C-esque伪代码的算法,但它有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;
}

基本上它执行普通的二进制搜索.它仅在最后一个案例的退货声明中有所不同,以满足额外要求.

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

#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

Answer 2

诡计

这里的技巧是搜索searchValue + 1并返回找到的索引，如index - 1下面left - 1的代码所示

例如，如果我们在 中搜索 9 [10, 20, 30]。该代码将查找 10 并返回它出现在第 0 个索引处，我们返回0-1的是-1

类似地，如果我们尝试在上面的示例中搜索 10，它将搜索10 + 1并返回第一个索引，我们返回1-1的是0

代码

def binary_search(array, searchValue, startIndex=0, endIndex=2 ** 32):
    """
    Binary search for the closest value less than or equal to the search value
    :param array: The given sorted list
    :param searchValue: Value to be found in the array
    :param startIndex: Initialized with 0
    :param endIndex: Initialized with 2**32
    :return: Returns the index closest value less than or equal to the search value
    """
    left = max(0, startIndex)
    right = min(len(array), endIndex)

    while left < right:
        mid = (left + right) // 2

        if array[mid] < searchValue + 1:
            left = mid + 1
        else:
            right = mid

    return left - 1

它也可以通过标准库在一行中完成。

import bisect
def standard_binary_search(array, searchVal):
    return bisect.bisect_left(array, searchVal + 1) - 1

测试

测试OP提供的测试用例

array = [10, 20, 30]
print(binary_search(array, 9))
print(binary_search(array, 10))
print(binary_search(array, 28))
print(binary_search(array, 5555))

结果

-1
 0
 1
 2

我创建了一个线性搜索来测试二分搜索。

-1
 0
 1
 2

以及一个测试上面所有二分查找函数的函数。检查正确性

def linear_search(array, searchVal):
    ans = -1
    for i, num in enumerate(array):
        if num > searchVal:
            return ans
        ans = i
    return ans

驱动功能

def check_correctness(array, searchVal):
    assert binary_search(array, searchVal) == linear_search(array, searchVal)
    assert binary_search(array, searchVal) == standard_binary_search(array, searchVal)
    return binary_search(array, searchVal)

驱动程序函数运行时没有任何断言错误。这就证明了上面两个函数的正确性。