Линейното търсене в Java винаги е било основният метод за намиране на елемент в масив. Той търси последователно всеки елемент от масива и е изключително лесен за изпълнение. Недостатъците на линейното търсене обаче са очевидни, когато въпросният масив съдържа десетки хиляди елементи. В такива случаи методът „разделяй и владей“, реализиран от Binary Search, е много по-ефективен и за предпочитане за програмисти, имащи предвид сложността на времето и пространството.
Двоично търсене
При двоично търсене масивът се разделя многократно на две половини, докато не бъде намерен ключът (елементът, който се търси). Разделянето е виртуално, т.е. запазва се целостта на данните. При всяка итерация се фокусира средната стойност на масива. Ако стойността е равна на ключа, който търсим, цикълът or рекурсивната функция прекратява. В противен случай продължава да зацикля. Ако средната стойност е по-голяма от ключа, тогава функцията се фокусира върху първата половина на масива и обратно. Този процес се повтаря, докато ключът бъде намерен or целият масив бъде повторен.
Разлика между линейно и двоично търсене
Линейно търсене |
Двоично търсене |
Последователно претърсва масива |
Разделя масива на две половини, докато се намери стойността |
Работи с всяHowви масиви |
Работи само със сортирани масиви |
Сложността е O(N) |
Сложността е O(log2N) |
Може да работи върху сортирани и несортирани масиви |
Може да се прилага само върху сортирани масиви. |
По-малко сложно за изпълнение |
По-сложен за изпълнение |
Алгоритъм за двоично търсене
Алгоритъмът на двоичното търсене е даден по-долу.
- Определете първата и последната точка на масива. Точките ще бъдат коригирани при всяка итерация според масива и търсения ключ.
- Превъртете през масива и сравнете средната стойност между текущата ви първа и последна точка. При първата итерация първата и последната променлива ще бъдат същите като действителните в масива.
- Ако ключът е по-голям от средната стойност, индексът на тази стойност ще бъде съхранен в новата променлива „Първа“.
- Ако ключът е по-малък от средната стойност, индексът на тази стойност ще бъде съхранен в променливата „Последна“.
- Това 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).
GO TO FULL VERSION