Гэты падручнік растлумачыць двайковы пошук & Рэкурсіўны двайковы пошук у Java разам з яго алгарытмам, рэалізацыяй і прыкладамі кода бінарнага пошуку Java:
Двайковы пошук у Java - гэта метад, які выкарыстоўваецца для пошуку мэтавага значэння або ключа ў калекцыі. Гэта тэхніка, якая выкарыстоўвае тэхніку «падзяляй і ўладар» для пошуку ключа.
Калекцыя, да якой будзе прымяняцца бінарны пошук для пошуку ключа, павінна быць адсартаваная ў парадку ўзрастання.
Звычайна большасць моў праграмавання падтрымліваюць метады лінейнага пошуку, двайковага пошуку і хэшавання, якія выкарыстоўваюцца для пошуку даных у калекцыі. Мы даведаемся пра хэшаванне ў нашых наступных падручніках.
Двайковы пошук у Java
Лінейны пошук з'яўляецца базавым метадам. У гэтай тэхніцы масіў праходзіць паслядоўна, і кожны элемент параўноўваецца з ключом, пакуль ключ не будзе знойдзены або не будзе дасягнуты канец масіва.
Лінейны пошук рэдка выкарыстоўваецца ў практычных прыкладаннях. Двайковы пошук з'яўляецца найбольш часта выкарыстоўванай тэхнікай, паколькі яна значна хутчэйшая за лінейны пошук.
Java забяспечвае тры спосабы выканання бінарнага пошуку:
- Выкарыстанне ітэратыўны падыход
- Выкарыстанне рэкурсіўнага падыходу
- Выкарыстанне метаду Arrays.binarySearch ().
У гэтым уроку мы ўкаранім і абмяркуем усе гэтыя 3 метады.
Алгарытм двайковага пошуку ў Java
У двайковым выглядземетад пошуку калекцыя шматразова дзеліцца на паловы, а ключавы элемент шукаецца ў левай ці правай палове калекцыі ў залежнасці ад таго, меншы ці большы за сярэдні элемент калекцыі.
Просты бінарны алгарытм пошуку выглядае наступным чынам:
- Вылічыце сярэдні элемент калекцыі.
- Параўнайце ключавыя элементы з сярэднім элементам.
- Калі ключ = сярэдні элемент, то мы вяртаем пазіцыю сярэдзіны індэкса для знойдзенага ключа.
- Інакш, калі ключ > сярэдні элемент, то ключ ляжыць у правай палове калекцыі. Такім чынам паўтарыце крокі з 1 па 3 у ніжняй (правай) палове калекцыі.
- Клавіша Else сярэдні элемент, то ключ знаходзіцца ў верхняй палове калекцыі. Такім чынам, вам трэба паўтарыць бінарны пошук у верхняй палове.
Як вы бачыце з прыведзеных вышэй крокаў, у двайковым пошуку палова элементаў у калекцыі ігнаруецца адразу пасля першага параўнання.
Звярніце ўвагу, што тая ж паслядоўнасць крокаў дзейнічае як для ітэратыўнага, так і для рэкурсіўнага двайковага пошуку.
Давайце праілюструем алгарытм бінарнага пошуку на прыкладзе.
Напрыклад, возьмем наступны адсартаваны масіў з 10 элементаў.
Давайце вылічым сярэдзіну масіва.
Сярэдзіна = 0+9/2 = 4
#1) Ключ = 21
Спачатку мы параўнаем значэнне ключа з [сярэдні] элемент, і мы знаходзім, што значэнне элемента ўmid = 21.
Такім чынам, мы знаходзім, што ключ = [mid]. Такім чынам, ключ знаходзіцца ў пазіцыі 4 у масіве.
#2) Ключ = 25
Спачатку мы параўнаем ключ значэнне да сярэдзіны. Як (21 25), мы будзем непасрэдна шукаць ключ у верхняй палове масіва.
Цяпер мы зноў знойдзем сярэдзіну для верхняй паловы масіва масіў.
Сярэдзіна = 4+9/2 = 6
Значэнне ў месцы [сярэдзіна] = 25
Цяпер мы параўнаць ключавы элемент з сярэднім элементам. Такім чынам, (25 == 25), такім чынам, мы знайшлі ключ у месцы [мід] = 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("\nKey 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("\nThe 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("\nKey not found in given list!"); else System.out.println("\nKey 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("\nThe 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("\nKey is not found in the array!"); else System.out.println("\nKey is found at index: "+result + " in the array."); } }
Вывад:
Уваходны масіў: [10, 20, 30, 40, 50, 60, 70, 80, 90]
Ключ для пошуку: 50
Ключ знаходзіцца па індэксе: 4 у масіве.
Часта задаюць пытанні
Q #1) Як вы пішаце двайковы пошук ?
Адказ: Двайковы пошук звычайна выконваецца шляхам падзелу масіва на паловы. Калі ключ для пошуку большы за сярэдні элемент,затым шукаецца верхняя палова масіва шляхам далейшага падзелу і пошуку падмасіўу, пакуль не будзе знойдзены ключ.
Аналагічным чынам, калі ключ меншы за сярэдні элемент, то ключ шукаецца ў ніжнім палова масіва.
Q #2) Дзе выкарыстоўваецца бінарны пошук?
Адказ: Двайковы пошук у асноўным выкарыстоўваецца для пошуку адсартаваныя даныя ў праграмных праграмах, асабліва калі прастора памяці кампактная і абмежаваная.
В #3) Што такое вялікае O двайковага пошуку?
Адказ : Часовая складанасць бінарнага пошуку роўная O (logn), дзе n — колькасць элементаў у масіве. Прасторавая складанасць двайковага пошуку роўная O (1).
В #4) Ці рэкурсіўны двайковы пошук?
Адказ: Так. Паколькі двайковы пошук з'яўляецца прыкладам стратэгіі "падзяляй і ўладар", і яго можна рэалізаваць з дапамогай рэкурсіі. Мы можам падзяліць масіў напалову і выклікаць адзін і той жа метад для выканання двайковага пошуку зноў і зноў.
В #5) Чаму гэта называецца бінарным пошукам?
Адказ: Алгарытм двайковага пошуку выкарыстоўвае стратэгію "падзяляй і ўладар", якая шматразова разразае масіў напалову або на дзве часткі. Таму яго называюць двайковым пошукам.
Выснова
Двайковы пошук з'яўляецца часта выкарыстоўваным метадам пошуку ў Java. Патрабаваннем для двайковага пошуку з'яўляецца тое, што даныя павінны быць адсартаваны ў парадку ўзрастання.
Двайковы пошук можа быцьрэалізаваны альбо з дапамогай ітэрацыйнага, альбо рэкурсіўнага падыходу. Клас Arrays у Java таксама забяспечвае метад "binarySearch", які выконвае двайковы пошук у масіве.
У нашых наступных падручніках мы будзем вывучаць розныя метады сартавання ў Java.