Java [binary search]

Java [binary search]

Мнениеот Jennifer » 20 Юни 2011 15:47

Здравейте. Става въпрос за 2 задачи за двоично търсене (Binary Search), върху които ще ме изпитват в сряда... Аз нищо не разбирам от NetBeans и Java. Моля ви много, помогнете ми; ако може и с обяснения? :sad: :sad:

1. Напишете програма, която да търси думи в масив и да ги извежда.

2. Напишете програма, която да избира от два масива с целочислени числа, такива, че тяхната сума да бъде 10 000.

Благодяря ви много предварително!! :( :) ;)

Jennifer
Нов
Нов
 
Мнения: 5
Регистриран на: 02 Мар 2011 20:27

Re: Java [binary search]

Мнениеот dannyboy » 21 Юни 2011 13:02

Код: Избери целия код
public class BinarySearch {

    //масива в който ще търсим
    public static int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};

    public static void main(String[] args){
        int elementToFind = 7; //елемента, за който ще търсим
        int position = binarySearch(elementToFind, 0, arr.length-1);
        if(position == -1)
            System.out.println("Елемента не е намерен");
        else
            System.out.println("Елемента е намерен на позиция "+(position+1));
    }

    //метод реализиращ двойчно търсене
    public static int binarySearch(int element, int left, int right){
        int l = left;
        int r = right;
        int m = (l+r)/2;
        while(l < = r){
            if(element == arr[m])
                return m;
            else if(element < arr[m])
                r = m - 1;
            else
                l = l + 1;
            m = (l+r)/2;
        }
        return -1; //ако не е намерен връщаме -1
    }
}


Двоичното търсене се основава на разделянето на дадено множество от записи на две равни части, сравняване на търсения идентификатор с последния запис от горната половина или с първия запис от долната половина и установяване по този начин в коя половина се намира той. Следва търсене в така откритата половина чрез нейното разделяне на две части и така нататък докато се стигне до желания запис. По този начин се намалява броят на четенията на записи и се спестява време от тази най-времеемка компютърна операция. Според теория на вероятностите при брой на записите n и последователно търсене средновероятният брой на четенията и свързаните с тях сравнения е n/2. При двоично търсене този брой е значително по-малък.
Аватар
dannyboy
Потребител
Потребител
 
Мнения: 122
Регистриран на: 16 Фев 2010 16:24
Местоположение: гр. Варна


Назад към PHP/Perl/Java/Python/ASP

Кой е на линия

Потребители разглеждащи този форум: 0 регистрирани и 1 госта

  • Реклама
cron