Binary search с Java

radi81 43 Точки

Binary search с Java

Здравейте, някой би ли погледнал къде греша? Това е задачата: Да се реализира двоично търсене (binary search) в сортиран целочислен масив.

public class BinarySearch {
public static int[] array = {2,3,6,7,9,10,11,14};

   public static void main(String[] args) {
       int value = 6;
       int position = binarySearch(value, 0, array.length-1 );

       if (position == -1) {
           System.out.println("Element is not found.");
       } else {
           System.out.printf("The position of element is: %d.", position);
       }
}

   public static int binarySearch(int element, int left, int right) {
       int l = left;
       int r = right;
       int m = l + (r-l)/2;
       while (l <= r) {
           if (element == array[m]) {
               return m;
           } else if (element > array[m]) {
               r = m-1;
           } else {
               l = m+1;
           }
           return -1;
       }
   }

}

Тагове:

30/08/2015 20:42:58 Fundamentals Module

Виж всички отговори

icaka98 3 Точки

Здравей,

Според мен грешката ти е, че когато element > array[m] , то тогава трябва l = m+1; (т.е. да увеличаваш долната граница), а в противен случай да намаляш горната r = m - 1. Дано не бъркам, но така изглежда. Друга грешка може да бъде това, че return -1 ти е в while - цикъла, а не трябва! Сигурно просто по невнимание :) Пробвай и ще видим. Дано съм помогнал, успех! :)

30/08/2015 21:19:01 30/08/2015 21:23:41

radi81 43 Точки

Благодаря за включването, знакът наистина е обърнат, но на това return място не можах да намеря. Не тръгва и това е.

30/08/2015 23:16:27

mgulubov 73 Точки

return -1; трябва да е извън scope-a на while цикъла. Пробвай така:

http://pastebin.com/e0XzvBKu

Също, част от идеята на binary search-a, е да можеш лесно да вкарваш елементи на коректните им места в списъка или иначе казано, да можеш да ползваш двойчно търсене, заедно с двойчно insert-ване, за да поддържаш една колекция подредена, а не да трябва да я сортираш отделно. За целта, когато binary search-a не намери търсения елемент, трябва да връща не -1, а индекса, където елемента би трябвало да стои, ако го имаше. Можеш да направиш следното - вместо return -1, да правиш return -(l + 1). Идеята е, че ако елемента го няма в колекцията, то евентуалното му място, ще е "l", само че, ако l == 0, няма как да провериш дали елемента е намерен или не :). За това, увеличаваш l с единица и връщаш резултата с - отпред. Там, където проверяваш резултата от търсенето, можеш да имаш нещо подобно - if (index < 0) {collection.insert(-(index + 1), element)} или иначе казано, ако получиш резултат -1, то ще знаеш, че елемента го няма в колекцията, но ако го имаше, то той щеше да е на позиция 0. Ако получиш -3, то по същата логика, елемента би бил на позиция 2.

Дано не съм те объркал още повече :D.

30/08/2015 23:34:28

radi81 43 Точки

Мерси, пробвах и така, но не тръгва. Определено мястото на return не е в while цикъла, но този път компилаторът хем не ми изписва грешка, хем програмата не спира да работи, а резултат никакъв не се изписва на конзолата.

31/08/2015 00:03:57

mgulubov 73 Точки

Хахаха виж, колко сме глупави :). Средния индекс, трябва да се преизчислява всеки път, когато има промяна по левия или десния индекс :). Изобщо не обърнах внимание :). Ето това, вече работи : http://pastebin.com/WpxAcdQu

31/08/2015 00:27:35

radi81 43 Точки

Пак не работи. Какво значат подчертаванията преди array, дава ми грешки там.

31/08/2015 12:02:52

icaka98 3 Точки

Те са просто част от името, може да ги махнеш ако името на твоя масив е само array. :)

31/08/2015 12:05:59

radi81 43 Точки

Ааа, работила си програмката, просто рестартирах Eclipse.

http://pastebin.com/BYXabQi8 - това е крайния вариант.

Само да добавя, че си намерих и още една грешка, в main метода в if-else трябваше да увелича position с 1, предполагам защото броенето на елементите в масива започва от 0. :)

31/08/2015 12:42:11

icaka98 3 Точки

Да, така е. Ако принтираш position само, то ще ти покаже индекса, където е намерено числото, а ако добавиш 1 ще ти покаже позицията. :) Браво, че работи и успех!

31/08/2015 13:23:41

Виж всички отговори