Распечатайте позицию повторяющихся чисел в массиве

Question

Итак, я пишу метод двоичного поиска, чтобы найти позицию в массиве числа, присвоенного ей. Верните эту позицию. Поэтому каждый раз, когда я сравниваю число в массиве с тем, что я ищу, распечатайте позицию в массиве и число в этой позиции. Ее мой код до сих пор:

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