Бінарний пошук. Допоможіть виправити помилку (java)

Коли число знайдено numberToFind в масиві — вивести номер відповідного елемента або −1 в іншому випадку.

public class BinarySearch {

	
public static void main(String[] args) {

	int data[] = { 3, 6, 7, 10, 34, 56, 60 };
		int numberToFind = 10;
        int i = 0;
        int j = data.length;
        int m = j/2;
       
        while(data[m]!=numberToFind & i < j){
            if(numberToFind > data[m]){
                i = m+1;
                m =((i+j)/2);
                }
            else {
                j = m-1;
                m =((i+j)/2);
                }
             
        }
        if (i > j){
    System.out.println("-1");
     }
    else {
    System.out.println(m);
        }
    }
}

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті

👍ПодобаєтьсяСподобалось0
До обраногоВ обраному0
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Скорее как некорректное использование (если только специально по каким-то причинам так не задумано).
А вообще у автора изначально проблема была в том, что условие в цикле не соответсвовало условию потом после цикла — противоположностью для

data[m]!=numberToFind && i < j
есть
data[m]==numberToFind || i >= j
(если еще не совсем старческий склероз и правильно помню законы де Моргана %))

Выход с цикла при истинности «data[m]!=numberToFind» возможен только если не выполнилась вторая часть условия. То есть если число не найдено, то однозначно i>=j.

В теории у него должно было всё заработать если просто «i>j» заменить на «i>=j», хотя и не так очевидно потом для чтения/понимания кода, как проверка на основе «data[m]==numberToFind»

Этот алгоритм лучше всего выражается через рекурсию. Тогда он действительно простой как 5 коп и работы на 5 — 10 мин.

Не факт. В коде выше в некоторых случаях может. Например, для 57.
Ну и топик стартеру внимательно смотреть на условие в цикле и читать теорию о приоритете операций %) Кроме того, если элемент заведомо не попадает в массив (меньше минимального или больше максимального) смысла «искать» нету.
ПС: как сказали ниже — не понимаешь где ошибка — отладчик в руки и вперед %))

Я просто оставлю это тут:
habrahabr.ru/post/91605

А вообще самое время учиться отлаживать свой код — дебаггер или отладочный вывод информации и вперёд до победного конца.

Благодарю за совет. Со статьей ознакомился,очень полезная інформация.

не особо вникав, но щось мені умова i < j не особо подобається

так, а що саме не працює?

Доброго дня, не працює

if (i > j){
System.out.println("-1″);

Попробуй реализовать данный алгоритм

Set L to 0 and R to n — 1.
If L > R, the search terminates as unsuccessful.
Set m (the position of the middle element) to the floor (the largest previous integer) of (L + R) / 2.
If Am < T, set L to m + 1 and go to step 2.
If Am > T, set R to m — 1 and go to step 2.
Now Am = T, the search is done; return m.
Это все завернул в цикл do while по условию m!=0 либо из цикла убираешь If L > R и do while делаешь по условию R>=L. И еще не пиши переменные i и j, не читабельно, вот если L и R уже хотя бы понятно что это левая и правая граница. Твой код почему возникает ошибка не проверял.

И так твой код исправил и все заработало
int data[] = { 3, 6, 7, 10, 34, 56, 60 };
int numberToFind = 4;
int i = 0;
int j = data.length-1; // если не делать −1 выйдем за границы массива при значении numberToFind > 60
int m = j/2;
int value;
while((value=data[m])!=numberToFind & i < j){
if(numberToFind > data[m]){
i = m+1;
m =(i+j)/2;
}
else {
j = m-1;
m =((i+j)/2);
}

}
if(data[m]==numberToFind){ // У тебя была ситуация когда i > j при том что значение элемента массива не совпадало с numberToFind. А тут уже есть такая проверка.
System.out.println(m);
}
else{
System.out.println(-1);
}

Заработало!!!Большое спасибо, да действительно проблема была в у словии

if (i > j)
, if (i == j) +
int j = data.length-1
 — это все что нужно было поменять для того чтобы программа заработала.

только value можно из кода убрать — она лишняя

Підписатись на коментарі