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

标签 duplicates binary-search

你好,

如果我们使用二进制搜索在以下数组中搜索 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));
    }
}

关于duplicates - 二进制搜索,如果数组包含重复项,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9702576/

相关文章:

java - 如何从旧实例创建新实例?

git - 创建 github 存储库的 "duplicate copy"

awk - awk如何仅在先前字段相同的情况下删除字段中的重复项

php - 如何检查我的MySQL表,以确保不会两次输入相同的内容?

performance - fortran中的二进制搜索效率与线性搜索效率

重新枚举具有唯一值的数据帧中的重复项

algorithm - 这个数组的二分查找需要多少次比较?

java - 将数据值添加到搜索算法?

java - 二进制搜索算法的正确方法

objective-c - 如何对 NSArray 进行二分查找?