Бесконечный цикл в бинарном варианте поиска (Java)

Question

Моя цель - ввести ключ и массив, а затем вывести количество значений в этом массиве, которые меньше или равны ключу, используя двоичный поиск.

Это мой код:

import java.util.*; 
import java.io.*; 

public class search { 
    public static void main(String[] args) { 
     Scanner scan = new Scanner(System.in); 
     int key = scan.nextInt(); 
     int size = scan.nextInt(); 
     int [] array = new int [size]; 

     for (int i = 0;i < size ;i++) { 
      array[i] = scan.nextInt(); 
     } 
     Arrays.sort(array); 

     System.out.println(binary(key, array)); 
    } 

    public static int binary (int key, int [] array){ 
     int lo = 0; 
     int hi = array.length - 1; 

     while (lo < hi){ 
      int mid = (lo + hi)/2; 
      if (array[mid] <= key){ 
       lo = mid; 
      } 

      else { 
       hi = mid - 1; 
      } 
     } 

     return lo + 1; 
    } 
} 

С ключом данных = 5, массив = {2,4,6,7}, программа работает нормально. Но в тот момент есть три значения, которые меньше или равны ключу, он идет с haywire. Например, key = 5, array = {2,4,5,6} создает бесконечный цикл. Я нашел причину этого, но я не вижу, как обойти это.

В основном значение mid продолжает рассчитываться как одно и то же значение. Что я могу сделать, чтобы обойти это? Если код по своей сути ошибочен, значит, the set solution for a USACO problem был неправильным.

Answer 1

Раствор образца кажется отлично. Проблема с вашим кодом в том, что mid = (lo + hi)/2 раундов по направлению к lo, что является проблемой, так как случаи обновления: lo = mid и hi = mid - 1. Когда hi == lo + 1, в первом случае прогресс не выполняется. Вы должны округлить, как показывает образец: mid = (lo + hi + 1)/2 (предупреждение: может переполняться на длинных массивах, проверьте свои ограничения).

Образец также проверяет, меньше ли первое значение, чем ключ.

Answer 2

Ваш алгоритм кажется прекрасным. Но я вижу, что есть проблема с назначением значения для середины.

int mid = (hi+lo)/2 

думать о том случае, когда ваш

hi=4 
mid = 3 

теперь новое значение среднего будет (3 + 4)/2 = 3 (целочисленное деление)

поэтому цикл будет продолжаться бег без лома.

В этом случае вы можете увеличить значение середины, проверив это условие.

Но более эффективно кажется, что лучше проверить значение середины повторения, Затем разбить петлю. На последней проверке является ли [привет] таким же, как ваш массив [середины]

Надеется, что это помогло бы значение массива ..

Иметь хороший день .. :)

EDIT

лучший способ сделать бы

Изменить время цикла для

while(mid<hi+1){ 
} 

затем проверить равенство значений после цикла ..

ИЛИ Просто установите

mid = (mid+hi+1)/2 

Answer 3

В вашей петле вы должны сделать свои интервалы меньше, и вы также должны исключить элемент, на который вы только что посмотрели. Вы делаете это, когда идете налево, но не тогда, когда идете вправо.

Вы также пропустите интервалы длины 1, потому что вы используете инклюзивные нижние и верхние границы. Условие цикла должно быть lo <= hi.

Наконец, вы возвращаете слишком много: результаты должны быть равны 0, когда ключ меньше первого элемента, и он должен быть длиной массива, когда он больше, чем последний элемент.

Итак:

static int binary(int key, int[] array) 
{ 
    int lo = 0; 
    int hi = array.length - 1; 

    while (lo <= hi) { 
     int mid = (lo + hi)/2; 

     if (array[mid] <= key) { 
      lo = mid + 1; 
     } else { 
      hi = mid - 1; 
     } 
    } 

    return lo; 
} 

На мой взгляд, лучше использовать эксклюзивный верхний предел, так как Java обычно делает. (Например, массив длиной n имеет элементы в indoces от 0 до n - 1, верхняя граница n находится за пределами допустимого диапазона.) Если ничего другого, оно согласуется с другим кодом Java. Итак:

static int binary(int key, int[] array) 
{ 
    int lo = 0; 
    int hi = array.length; 

    while (lo < hi) { 
     int mid = (lo + hi)/2; 

     if (array[mid] <= key) { 
      lo = mid + 1; 
     } else { 
      hi = mid; 
     } 
    } 

    return lo; 
}