如果数组包含重复项则进行二分查找

Hi,

如果我们使用二分搜索在以下数组中搜索 24，则搜索键的索引是多少。

array = [10,20,21,24,24,24,24,24,30,40,45]

我对二分搜索有疑问，如果数组有重复值，它是如何工作的。任何人都可以澄清吗？

您建议的数组在中间索引中具有目标值，并且在最有效的实现中将在第一级递归之前返回该值。此实现将返回“5”（中间索引）。

要理解该算法，只需在调试器中单步执行代码即可。

public class BinarySearch {
    public static int binarySearch(int[] array, int value, int left, int right) {
          if (left > right)
                return -1;
          int middle = left + (right-left) / 2;
          if (array[middle] == value)
                return middle;
          else if (array[middle] > value)
                return binarySearch(array, value, left, middle - 1);
          else
                return binarySearch(array, value, middle + 1, right);           
    }

    public static void main(String[] args) {
        int[] data = new int[] {10,20,21,24,24,24,24,24,30,40,45};

        System.out.println(binarySearch(data, 24, 0, data.length - 1));
    }
}