Двоично търсене в Java: рекурсивни, итеративни и Java колекции

Линейното търсене в Java винаги е било основният метод за намиране на елемент в масив. Той търси последователно всеки елемент от масива и е изключително лесен за изпълнение. Недостатъците на линейното търсене обаче са очевидни, когато въпросният масив съдържа десетки хиляди елементи. В такива случаи методът „разделяй и владей“, реализиран от Binary Search, е много по-ефективен и за предпочитане за програмисти, имащи предвид сложността на времето и пространството.

Двоично търсене

При двоично търсене масивът се разделя многократно на две половини, докато не бъде намерен ключът (елементът, който се търси). Разделянето е виртуално, т.е. запазва се целостта на данните. При всяка итерация се фокусира средната стойност на масива. Ако стойността е равна на ключа, който търсим, цикълът or рекурсивната функция прекратява. В противен случай продължава да зацикля. Ако средната стойност е по-голяма от ключа, тогава функцията се фокусира върху първата половина на масива и обратно. Този процес се повтаря, докато ключът бъде намерен or целият масив бъде повторен.

Разлика между линейно и двоично търсене

Алгоритъм за двоично търсене

Алгоритъмът на двоичното търсене е даден по-долу.

1. Определете първата и последната точка на масива. Точките ще бъдат коригирани при всяка итерация според масива и търсения ключ.
2. Превъртете през масива и сравнете средната стойност между текущата ви първа и последна точка. При първата итерация първата и последната променлива ще бъдат същите като действителните в масива.
3. Ако ключът е по-голям от средната стойност, индексът на тази стойност ще бъде съхранен в новата променлива „Първа“.
4. Ако ключът е по-малък от средната стойност, индексът на тази стойност ще бъде съхранен в променливата „Последна“.
5. Това condition се повтаря, докато едно от двете условия стане истина:
   • Ключът е намерен.
   • Целият масив е повторен.

Кодът Howто за итеративно двоично търсене, така и за рекурсивно двоично търсене е даден по-долу.

Итеративно двоично търсене

Кодът за двоично търсене с итеративен метод е даден по-долу.

import java.util.Scanner;
public class IterativeBinarySearch {
 
    public static void main(String[] args) {
        int arr[] = {1,3,6,8,10};
       
        System.out.println("Enter Number to Search For: ");
        Scanner input = new Scanner (System.in);
       
        int num = input.nextInt();
        int result = BinarySearchIterative(arr,num);
       
        if(result!=-1)
            System.out.println("Value Found at Index #" + result);
        else
            System.out.println("Value Not Found");
    }
 
    public static int BinarySearchIterative(int[] arr, int num){
        //Representing the Start and End Index After Division of Array
        int start = 0;
        int end = arr.length;
 
        //Loop to Iterate Through the Array
        for(int i = 0; iarr[n]){
                start = n;
            }
            //If number to search for is greater than the arr value at index 'n'               
            else{
                end = n;
            }
        }
        //If number isn't found, return -1
        return -1;
    }
}

Рекурсивно двоично търсене

Кодът за двоично използване на рекурсия е даден по-долу.

import java.util.Scanner;
public class RecursiveBinarySearch {
 
    public static void main(String[] args) {
        int arr[] = {1,3,6,8,10};
 
        System.out.println("Enter Number to Search For: ");
        Scanner input = new Scanner (System.in);
 
        int num = input.nextInt();
        int result = BinarySearchRecursive(arr,0,arr.length-1,num);
 
        if(result!=-1)
            System.out.println("Value Found at Index #" + result);
        else
            System.out.println("Value Not Found");
    }
 
public static int BinarySearchRecursive(int arr[], int a, int b, int num){
    //Base Case to Exit the Recursive Function
    if (b < 1) {
        return -1;
    }
        int n = a + (b=1)/2;
 
       //If number is found at mean index of start and end
        if(arr[n]==num)
            return n;
 
       //If number to search for is greater than the arr value at index 'n'
        else if(arr[n]>num)
            return BinarySearchRecursive(arr,a,n-1,num);
 
       //If number to search for is greater than the arr value at index 'n'
        else
            return BinarySearchRecursive(arr,n+1,b,num);
    }
 
}

Времева сложност

С всяка следваща итерация, масивът, т.е. пространството за търсене, се разделя наполовина. След всяка итерация 'm' пространството за търсене ще се промени до размер N/2m. В най-лошия случай ще останем само с един елемент от едната далечна страна на масива. По това време сложността на двоичното търсене ще бъде k = log2N. Времевата сложност на линейното търсене е O(N), което води до много по-бързо двоично търсене със сложността O(log2N). Това е основното предимство от използването на двоично търсене пред линейно търсене.

Космическа сложност

Двоичното търсене използва три различни променливи - начало, край и среда. Тези три променливи са създадени като указатели, които сочат към местоположението на паметта на индексите на масива. Поради това двоичното търсене е изключително ефективно с пространство. Пространствената сложност на итеративното двоично търсене е O(1). За рекурсивна реализация е O(log N).