二进制搜索,如果数组包含重复项

Question

嗨,

如果我们使用二进制搜索在以下数组中搜索24,那么搜索键的索引是什么.

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

我对二进制搜索有疑问,如果数组有重复值,它是如何工作的.任何人都可以澄清...

Answer 1

您建议的数组在中间索引中具有目标值,并且在最有效的实现中将在第一级递归之前返回此值.此实现将返回'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));
    }
}