binary search algorithm java implementation examples
Този урок ще обясни двоично търсене и рекурсивно двоично търсене в Java заедно с неговите примери за алгоритъм, внедряване и Java двоичен код за търсене:
Двоичното търсене в Java е техника, която се използва за търсене на целева стойност или ключ в колекция. Това е техника, която използва техниката „разделяй и владей“ за търсене на ключ.
Колекцията, върху която трябва да се приложи двоично търсене за търсене на ключ, трябва да бъде сортирана във възходящ ред.
Обикновено повечето от езиците за програмиране поддържат техники за линейно търсене, двоично търсене и хеширане, които се използват за търсене на данни в колекцията. Ще научим хеширането в следващите ни уроци.
=> Посетете тук, за да научите Java от нулата.
Какво ще научите:
Двоично търсене в Java
Линейното търсене е основна техника. При тази техника масивът се обхожда последователно и всеки елемент се сравнява с ключа, докато ключът бъде намерен или не бъде достигнат краят на масива.
Линейното търсене се използва рядко в практически приложения. Бинарното търсене е най-често използваната техника, тъй като е много по-бързо от линейното търсене.
Java предоставя три начина за извършване на двоично търсене:
как да стартирам jar файл -
- Използване на итеративен подход
- Използване на рекурсивен подход
- Използване на метода Arrays.binarySearch ().
В този урок ще внедрим и обсъдим всички тези 3 метода.
Алгоритъм за двоично търсене в Java
При двоичния метод за търсене колекцията се разделя многократно на половина и ключовият елемент се търси в лявата или дясната половина на колекцията в зависимост от това дали ключът е по-малък или по-голям от средния елемент на колекцията.
Един прост алгоритъм за двоично търсене е както следва:
- Изчислете средния елемент на колекцията.
- Сравнете ключовите елементи със средния елемент.
- Ако ключ = среден елемент, тогава връщаме средната позиция на индекса за намерения ключ.
- Else Ако ключ> среден елемент, тогава ключът се намира в дясната половина на колекцията. По този начин повторете стъпки от 1 до 3 в долната (дясната) половина на колекцията.
- Друг ключ
Както можете да видите от горните стъпки, при двоично търсене половината елементи в колекцията се игнорират веднага след първото сравнение.
Имайте предвид, че същата последователност от стъпки е валидна както за итеративно, така и за рекурсивно двоично търсене.
Нека илюстрираме двоичен алгоритъм за търсене на пример.
Например, вземете следния сортиран масив от 10 елемента.
Нека изчислим средното местоположение на масива.
Mid = 0 + 9/2 = 4
# 1) Ключ = 21
Първо ще сравним стойността на ключа с елемента [mid] и ще установим, че стойността на елемента в средата = 21.
Така намираме този ключ = [mid]. Следователно ключът се намира на позиция 4 в масива.
разлика в c и c ++
# 2) Ключ = 25
Първо сравняваме ключовата стойност със средата. Както (21<25), we will directly search for the key in the upper half of the array.
Сега отново ще намерим средата за горната половина на масива.
Средно = 4 + 9/2 = 6
Стойността в местоположението [mid] = 25
Сега сравняваме ключовия елемент със средния елемент. И така (25 == 25), следователно намерихме ключа на място [mid] = 6.
Така многократно разделяме масива и като сравняваме ключовия елемент със средата, решаваме в коя половина да търсим ключа. Двоичното търсене е по-ефективно по отношение на времето и коректността и също е много по-бързо.
Изпълнение на двоично търсене Java
Използвайки горния алгоритъм, нека внедрим програма за двоично търсене в Java, използвайки итеративен подход. В тази програма вземаме примерен масив и извършваме двоично търсене на този масив.
import java.util.*; class Main{ public static void main(String args[]){ int numArray[] = {5,10,15,20,25,30,35}; System.out.println('The input array: ' + Arrays.toString(numArray)); //key to be searched int key = 20; System.out.println('
Key to be searched=' + key); //set first to first index int first = 0; //set last to last elements in array int last=numArray.length-1; //calculate mid of the array int mid = (first + last)/2; //while first and last do not overlap while( first <= last ){ //if the mid < key, then key to be searched is in the first half of array if ( numArray[mid] last ){ System.out.println('Element is not found!'); } } }
Изход:
Входният масив: [5, 10, 15, 20, 25, 30, 35]
Ключ за търсене = 20
Елементът е намерен в индекс: 3
Горната програма показва итеративен подход на двоично търсене. Първоначално се декларира масив, след което се дефинира ключ за търсене.
След изчисляване на средата на масива, ключът се сравнява със средния елемент. След това в зависимост от това дали ключът е по-малък или по-голям от ключа, ключът се търси съответно в долната или горната половина на масива.
Рекурсивно двоично търсене в Java
Можете също да извършите двоично търсене, използвайки техниката на рекурсията. Тук бинарният метод за търсене се извиква рекурсивно, докато ключът бъде намерен или целият списък бъде изчерпан.
Програмата, която прилага рекурсивно двоично търсене, е дадена по-долу:
import java.util.*; class Main{ //recursive method for binary search public static int binary_Search(int intArray[], int low, int high, int key){ //if array is in order then perform binary search on the array if (high>=low){ //calculate mid int mid = low + (high - low)/2; //if key =intArray[mid] return mid if (intArray[mid] == key){ return mid; } //if intArray[mid] > key then key is in left half of array if (intArray[mid] > key){ return binary_Search(intArray, low, mid-1, key);//recursively search for key }else //key is in right half of the array { return binary_Search(intArray, mid+1, high, key);//recursively search for key } } return -1; } public static void main(String args[]){ //define array and key int intArray[] = {1,11,21,31,41,51,61,71,81,91}; System.out.println('Input List: ' + Arrays.toString(intArray)); int key = 31; System.out.println('
The key to be searched:' + key); int high=intArray.length-1; //call binary search method int result = binary_Search(intArray,0,high,key); //print the result if (result == -1) System.out.println('
Key not found in given list!'); else System.out.println('
Key is found at location: '+result + ' in the list'); } }
Изход:
Списък на входните данни: [1, 11, 21, 31, 41, 51, 61, 71, 81, 91
Ключът за търсене:
Ключът се намира на място: 3 в списъка
Използване на метода Arrays.binarySearch ().
Класът Arrays в Java предоставя метод ‘binarySearch ()’, който извършва бинарното търсене на дадения масив. Този метод приема масива и ключа за търсене като аргументи и връща позицията на ключа в масива. Ако ключът не е намерен, тогава методът връща -1.
Примерът по-долу реализира метода Arrays.binarySearch ().
import java.util.Arrays; class Main{ public static void main(String args[]){ //define an array int intArray[] = {10,20,30,40,50,60,70,80,90}; System.out.println('The input Array : ' + Arrays.toString(intArray)); //define the key to be searched int key = 50; System.out.println('
The key to be searched:' + key); //call binarySearch method on the given array with key to be searched int result = Arrays.binarySearch(intArray,key); //print the return result if (result <0) System.out.println('
Key is not found in the array!'); else System.out.println('
Key is found at index: '+result + ' in the array.'); } }
Изход:
Входният масив: [10, 20, 30, 40, 50, 60, 70, 80, 90]
Ключът за търсене: 50
Ключът се намира в индекс: 4 в масива.
често задавани въпроси
В # 1) Как се пише двоично търсене?
Отговор: Бинарното търсене обикновено се извършва чрез разделяне на масива на половинки. Ако ключът, който трябва да се търси, е по-голям от средния елемент, тогава горната половина на масива се търси чрез по-нататъшно разделяне и търсене на под-масива, докато ключът бъде намерен.
По същия начин, ако ключът е по-малък от средния елемент, тогава ключът се търси в долната половина на масива.
В # 2) Къде се използва бинарното търсене?
Отговор: Бинарното търсене се използва главно за търсене на сортирани данни в софтуерни приложения, особено когато паметта е компактна и ограничена.
В # 3) Кое е голямото O на двоичното търсене?
Отговор: Сложността във времето на двоичното търсене е O (logn), където n е броят на елементите в масива. Сложността на пространството на бинарното търсене е O (1).
В # 4) Рекурсивно ли е бинарното търсене?
Отговор: Да. Тъй като двоичното търсене е пример за стратегия „разделяй и владей“ и може да бъде приложено с помощта на рекурсия. Можем да разделим масива на половинки и да извикаме същия метод, за да извършим бинарното търсене отново и отново.
В # 5) Защо се нарича двоично търсене?
Отговор: Алгоритъмът за двоично търсене използва стратегия за разделяне и завладяване, която многократно разрязва масива на половинки или две части. По този начин той се нарича двоично търсене.
Заключение
Двоичното търсене е често използваната техника за търсене в Java. Изискването за извършване на двоично търсене е данните да бъдат сортирани във възходящ ред.
Двоичното търсене може да бъде реализирано или чрез итеративен, или с рекурсивен подход. Класът Arrays в Java също предоставя метода ‘binarySearch’, който извършва двоично търсене на масив.
В следващите ни уроци ще изследваме различни техники за сортиране в Java.
етапи от жизнения цикъл на разработването на софтуер
=> Внимавайте тук за простия сериал за обучение на Java.
Препоръчително четене
- Сортиране на селекция в Java - Алгоритъм за сортиране на селекция и примери
- Сортиране при вмъкване в Java - Алгоритъм за сортиране при вмъкване и примери
- Двоично дърво за търсене C ++: Внедряване на BST и операции с примери
- Урок за интерфейс на Java и абстрактен клас с примери
- Урок за JAVA за начинаещи: 100+ практически ръководства за Java видео
- Сортиране на балончета в Java - алгоритми за сортиране на Java и примери за кодове
- Java урок за низове | Низови методи на Java с примери
- Какво е Java Vector | Урок за Java Vector Class с примери