二进制搜索数组是否包含重复项 [英] Binary search if array contains duplicates

问题描述

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

what is the index of the search key if we search for 24 in the following array using binary search.

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

我对二进制搜索有疑问，如果数组中有重复的值，二进制搜索如何工作.有人可以澄清一下吗……

I have a doubt regarding binary search that how does it works if a array has duplicate values.Can anybody clarify...

推荐答案

您提出的数组的目标值位于中间索引中，在最有效的实现中，该数组将在第一级递归之前返回该值.此实现将返回"5"(中间索引).

The array you proposed has the target value in the middle index, and in the most efficient implementations will return this value before the first level of recursion. This implementation would return '5' (the middle index).

要了解算法，只需在调试器中逐步执行代码即可.

To understand the algorithm, just step through the code in a debugger.

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

这篇关于二进制搜索数组是否包含重复项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！