Ikkilangan qidirish Java'da xato

Bu ikkilik qidiruvga menga nima bo'lganini aniqlash uchun berilgan. Xatning sharhlari bor, shuning uchun o'ylashim mumkin bo'lgan yagona narsa - bu chiziqni olib tashlash, deb o'ylamayman. Bundan tashqari, yo'qolgan narsa haqida o'ylay olmayman - bu haqiqatdan ham noto'g'ri narsa bormi?

public boolean search(int val) {
    int low = 0;
    int high = size-1;
    int middle = -1;
    boolean found = false;
    while (!found && low < high) {
        middle = low + (high-low)/2;
        if (a[middle] == val)
           found = true;
        else if (a[middle] < val)
           low = middle + 1;
        else//(a[middle] > val)
           high = middle - 1;
    }
    return found;
}
1
Fikr bir narsani aniqlab beradi - ! (A [middle] == val) va ! (A [middle] else val) ga teng bo'lsa, unda teng bo'lmasa va undan katta bo'lmasa.
qo'shib qo'ydi muallif OldCurmudgeon, manba
Muammoni o'zingiz topishingiz mumkin. [1,2] qatorini kiriting va 2 ni qidiring.
qo'shib qo'ydi muallif OldCurmudgeon, manba
Muammoni o'zingiz topishingiz mumkin. [1,2] qatorini kiriting va 2 ni qidiring.
qo'shib qo'ydi muallif OldCurmudgeon, manba

6 javoblar

Sizning qatoringizda 2 ta qadriyatlar bo'lganingizda ishni ko'rib chiqamiz: [0, 1] va siz qiymatni qidirasiz 1. Kodni ishga tushamiz:

int low = 0;
int high = size-1;//high = 1
int middle = -1;
boolean found = false;
while (!found && low < high) {
    middle = low + (high-low)/2;//middle = 0 + (1-0)/2 = 0
    if (a[middle] == val)//FALSE (because a[0] = 0)
       found = true;
    else if (a[middle] < val)//TRUE (because a[0] = 0 and 0 < 1)
       low = middle + 1; //low = 0 + 1 = 1
    else//(a[middle] > val)
       high = middle - 1;
}
return found;

Because low = 1, you get out of the loop since you have a condition low < high and your return false, even though 1 is present in your array.

Muammo middle = low + (high-low)/2; foydalanadi va u yumaloq bo'ladi.

1
qo'shib qo'ydi

Sizning qatoringizda 2 ta qadriyatlar bo'lganingizda ishni ko'rib chiqamiz: [0, 1] va siz qiymatni qidirasiz 1. Kodni ishga tushamiz:

int low = 0;
int high = size-1;//high = 1
int middle = -1;
boolean found = false;
while (!found && low < high) {
    middle = low + (high-low)/2;//middle = 0 + (1-0)/2 = 0
    if (a[middle] == val)//FALSE (because a[0] = 0)
       found = true;
    else if (a[middle] < val)//TRUE (because a[0] = 0 and 0 < 1)
       low = middle + 1; //low = 0 + 1 = 1
    else//(a[middle] > val)
       high = middle - 1;
}
return found;

Because low = 1, you get out of the loop since you have a condition low < high and your return false, even though 1 is present in your array.

Muammo middle = low + (high-low)/2; foydalanadi va u yumaloq bo'ladi.

1
qo'shib qo'ydi

Kodni o'qib chiqing va kodni oson o'qib chiqing.

middle = low + (high-low)/2;
if (a[middle] == val) {
  found = true;
  break;
}

if (a[middle] < val) {
  low = middle + 1; 
} else { 
  high = middle - 1;
}

I think now it becomes clearer, what that comment is really saying - it simply expresses that this is the case when a[middle] > val.

0
qo'shib qo'ydi
Arzimaydi; faqatgina rekord uchun: bunday muammolarni disk raskadrovka qilish ... dasturiy dasturlarning muhim qismidir. Buning uchun tuzatishni tomoniga SO ga o'girish kerak emas. Xato ayıklayıcısını foydalanishni bilib oling; yoki hech bo'lmaganda o'zingizning kodingizga qanday qilib izlanishlar haqida ma'lumot qo'shishni taklif qilishingiz mumkin, shuning uchun amal qiling nima qilishini bilib oling.
qo'shib qo'ydi muallif GhostCat, manba
Rahmat, afsuski, bu tushuntirilganda aniq ko'rinadi!
qo'shib qo'ydi muallif user7553755, manba

Kodni o'qib chiqing va kodni oson o'qib chiqing.

middle = low + (high-low)/2;
if (a[middle] == val) {
  found = true;
  break;
}

if (a[middle] < val) {
  low = middle + 1; 
} else { 
  high = middle - 1;
}

I think now it becomes clearer, what that comment is really saying - it simply expresses that this is the case when a[middle] > val.

0
qo'shib qo'ydi
Arzimaydi; faqatgina rekord uchun: bunday muammolarni disk raskadrovka qilish ... dasturiy dasturlarning muhim qismidir. Buning uchun tuzatishni tomoniga SO ga o'girish kerak emas. Xato ayıklayıcısını foydalanishni bilib oling; yoki hech bo'lmaganda o'zingizning kodingizga qanday qilib izlanishlar haqida ma'lumot qo'shishni taklif qilishingiz mumkin, shuning uchun amal qiling nima qilishini bilib oling.
qo'shib qo'ydi muallif GhostCat, manba
Rahmat, afsuski, bu tushuntirilganda aniq ko'rinadi!
qo'shib qo'ydi muallif user7553755, manba

Qo'ng'iroq qilayotgan qatorni [1,2] bo'lsin.

Kodni yuring:

Start: low = 0, high = 1. Step1: middle = 0 - no match (1 < 2) so low = 1. Loop check - low < high? NO - stop searching.

0
qo'shib qo'ydi

Qo'ng'iroq qilayotgan qatorni [1,2] bo'lsin.

Kodni yuring:

Start: low = 0, high = 1. Step1: middle = 0 - no match (1 < 2) so low = 1. Loop check - low < high? NO - stop searching.

0
qo'shib qo'ydi