Професионална програма
Loading...
radi81 avatar 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;
        }
    }
    
}

 

Тагове:
0
Fundamentals Module
icaka98 avatar icaka98 3 Точки

Здравей,

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

1
30/08/2015 21:23:41
radi81 avatar radi81 43 Точки

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

0
mgulubov avatar 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.

 

1
radi81 avatar radi81 43 Точки

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

0
mgulubov avatar mgulubov 73 Точки

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

0
radi81 avatar radi81 43 Точки

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

0
icaka98 avatar icaka98 3 Точки

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

0
radi81 avatar radi81 43 Точки

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

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

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

0
icaka98 avatar icaka98 3 Точки

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

0