打印出数组中重复数字的位置

Question

所以我正在编写一个二进制搜索方法来查找给定的数字在数组中的位置。 Return那个位置。所以每次我将数组中的数字与我正在搜索的数字进行比较时，打印出数组中的位置和该位置的数字。到目前为止，她是我的代码：

public static int binSearch(int[] arr, int key) {
    int lo = 0;
    int hi = array.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (key < arr[mid]) { 
           hi = mid - 1;
        } else if (key > arr[mid]) {
           lo = mid + 1;
        }
        else {
           return mid;
        }
    }
    return -1;
}

public static void main(String[] arg) {

    int[] array = new int[] { 0, 1, 2, 2, 2, 3, 3, 4};

    for ( int i = 0; i < array.length; i++ ) {
        int index = Arrays.binarySearch(array, i);
        System.out.println(array[i] + " at " + index);
    }
}

输出：

 0 at 0
 1 at 1
 2 at 2
 2 at 5
 2 at 8
 3 at 9
 3 at 10
 4 at -12
 4 at 11

我的预期输出是

 0 at 0
 1 at 1
 2 at 2
 2 at 3
 2 at 4
 3 at 5
 3 at 6
 4 at 7
 4 at 8

感谢您的帮助！

Answer 1

您将 index 而不是 element 传递给二进制搜索函数。

试试这个

for ( int i = 0; i < array.length; i++ ) {
    int index = binarySearch(array, array[i]);
    System.out.println(array[i] + " at " + index);
}

而且你的二分查找功能也有一些问题..

这是更正后的

static int binarySearch(int[] arr, int key) { //Changed name to match with calling function name
int lo = 0;
int hi = arr.length - 1; //not array.length
while (lo <= hi) {

    int mid = lo + (hi - lo) / 2;
    if (key < arr[mid]) { 
       hi = mid - 1;
    } else if (key > arr[mid]) 
       lo = mid + 1;
    // you had one } here
    else return mid;
 }
 return -1;
}

这会产生输出

0 at 0
1 at 1
2 at 3
2 at 3
2 at 3
3 at 5
3 at 5
4 at 7

使用 binary search 生成您提到的输出有什么用？。要获得您提到的输出，您可以使用 linear search.

Answer 2

如果array按照Arrays.binarySearch方法的要求排序，第一项的索引很容易找到：

int index= Arrays.binarySearch(array, value);

负结果表示 value 不在 array 中。现在，如果找到并且您对其他索引感兴趣，您可以简单地遍历数组直到值不再匹配：

public static void printIndexes(int[] array, int value){
  int index= Arrays.binarySearch(array, value);
  if (index < 0){
    return; // value not in array
  }
  while (index < array.length && array[index]==value){
    System.out.println(value + " at " + index);
    index++;
  }
}

打印出数组中重复数字的位置

Print out position of duplicate numbers in an array

java

arrays

search

duplicates