Двійковий пошук є одним із методів пошуку, який застосовується під час сортування вхідних даних. Тут ми зосереджуємося на пошуку середнього елемента, який діє як референтний кадр, незалежно від того, слід переходити до нього ліворуч чи праворуч, оскільки елементи вже відсортовано. Цей пошук допомагає оптимізувати техніку пошуку з кожною ітерацією, називається двійковим пошуком, і читачі наголошують на ньому, оскільки він опосередковано застосовується під час вирішення питань.
Алгоритм двійкового пошуку в Java
Нижче наведено алгоритм, розроблений для бінарного пошуку:
- Почніть
- Візьміть вхідний масив і Target
- Ініціалізувати початок = 0 і кінець = (розмір масиву -1)
- Індіанізувати середню змінну
- середина = (початок+кінець)/2
- if array[ mid ] == target then return mid
- якщо масив [середина]
- if array[ mid ]> target then end = mid-1
- якщо початок<=кінець, то перейдіть до кроку 5
- повертає -1 як елемент не знайдено
- Вихід
Тепер ви, мабуть, думаєте, що якщо вхідні дані не відсортовано, то результати будуть невизначеними.
Примітка: Якщо є дублікати, немає гарантії, який саме буде знайдено.
Методи двійкового пошуку Java
У Java є три методи для реалізації Двійковий пошук в Java згадані нижче:
- Ітераційний метод
- Рекурсивний метод
- Метод вбудованої збірки
1. Ітеративний метод бінарного пошуку в Java
Нижче наведено реалізацію:
Java
// Java implementation of iterative Binary Search> class> BinarySearch {> >// Returns index of x if it is present in arr[l....r], else return -1> >int> binarySearch(>int> arr[],>int> l,>int> r,>int> x)> >{> >while> (l <= r) {> >int> mid = (l + r) />2>;> >// If the element is present at the> >// middle itself> >if> (arr[mid] == x) {> >return> mid;> >// If element is smaller than mid, then> >// it can only be present in left subarray> >// so we decrease our r pointer to mid - 1> >}>else> if> (arr[mid]>x) {> >r = mid ->1>;> >// Else the element can only be present> >// in right subarray> >// so we increase our l pointer to mid + 1> >}>else> {> >l = mid +>1>;> >}> >}> >// We reach here when element is not present> >// in array> >return> ->1>;> >}> >// Driver method to test above> >public> static> void> main(String args[])> >{> >BinarySearch ob =>new> BinarySearch();> >int> arr[] = {>2>,>3>,>4>,>10>,>40> };> >int> n = arr.length;> >int> x =>10>;> >int> result = ob.binarySearch(arr,>0>, n ->1>, x);> >if> (result == ->1>)> >System.out.println(>'Element not present'>);> >else> >System.out.println(>'Element found at index '> >+ result);> >}> }> |
>
>Вихід
сортування списку за java
Element found at index 3>
Порада: Виродки, мабуть, цікавляться, чи існує така функція нижня_межа() або upper_bound() просто, ймовірно, знайдено в C++ STL. тож пряма відповідь полягає в тому, що функції не було лише до Java 9, пізніше вони були додані.
2. Рекурсивний метод бінарного пошуку
Нижче наведено реалізацію вищезазначеного методу:
Java
// Java implementation of> // recursive Binary Search> // Driver Class> class> BinarySearch {> >// Returns index of x if it is present in arr[l..> >// r], else return -1> >int> binarySearch(>int> arr[],>int> l,>int> r,>int> x)> >{> >if> (r>= l) {> >int> mid = l + (r - l) />2>;> >// If the element is present at the> >// middle itself> >if> (arr[mid] == x)> >return> mid;> >// If element is smaller than mid, then> >// it can only be present in left subarray> >if> (arr[mid]>x)> >return> binarySearch(arr, l, mid ->1>, x);> >// Else the element can only be present> >// in right subarray> >return> binarySearch(arr, mid +>1>, r, x);> >}> >// We reach here when element is not present> >// in array> >return> ->1>;> >}> >// main function> >public> static> void> main(String args[])> >{> >BinarySearch ob =>new> BinarySearch();> >int> arr[] = {>2>,>3>,>4>,>10>,>40> };> >int> n = arr.length;> >int> x =>10>;> >int> result = ob.binarySearch(arr,>0>, n ->1>, x);> >if> (result == ->1>)> >System.out.println(> >'Element is not present in array'>);> >else> >System.out.println(> >'Element is present at index '> + result);> >}> }> |
>
>Вихід
Element is present at index 3>
Складність описаного вище способу
Часова складність: O(log N)
Космічна складність: O(1), якщо розглядається стек рекурсивних викликів, то допоміжний простір буде O(log N)
3. У Метод побудови для бінарного пошуку в Java
Arrays.binarysearch() працює для масивів, які також можуть мати простий тип даних.
Нижче наведено реалізацію вищезазначеного методу:
Java
// Java Program to demonstrate working of binarySearch()> // Method of Arrays class In a sorted array> // Importing required classes> import> java.util.Arrays;> // Main class> public> class> GFG {> >// Main driver method> >public> static> void> main(String[] args)> >{> >// Declaring an integer array> >int> arr[] = {>10>,>20>,>15>,>22>,>35> };> >// Sorting the above array> >// using sort() method of Arrays class> >Arrays.sort(arr);> >int> key =>22>;> >int> res = Arrays.binarySearch(arr, key);> >if> (res>=>0>)> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >key =>40>;> >res = Arrays.binarySearch(arr, key);> >if> (res>=>0>)> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >}> }> |
>
>Вихід
22 found at index = 3 40 Not found>
Двійковий пошук у колекціях Java
Тепер давайте подивимося, як Collections.binarySearch() працює для LinkedList. Отже, як було сказано вище, цей метод виконується за log(n) час для списку довільного доступу, наприклад ArrayList. Якщо вказаний список не реалізує інтерфейс RandomAccess і є великим, цей метод виконає бінарний пошук на основі ітератора, який виконує O(n) обходів посилань і O(log n) порівнянь елементів.
Collections.binarysearch() працює для таких об’єктів, як колекції ArrayList і LinkedList .
Нижче наведено реалізацію вищезазначеного методу:
Java
// Java Program to Demonstrate Working of binarySearch()> // method of Collections class> // Importing required classes> import> java.util.ArrayList;> import> java.util.Collections;> import> java.util.List;> // Main class> public> class> GFG {> >// Main driver method> >public> static> void> main(String[] args)> >{> >// Creating an empty ArrayList of integer type> >List al =>new> ArrayList();> >// Populating the Arraylist> >al.add(>1>);> >al.add(>2>);> >al.add(>3>);> >al.add(>10>);> >al.add(>20>);> >// 10 is present at index 3> >int> key =>10>;> >int> res = Collections.binarySearch(al, key);> >if> (res>=>0>)> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >key =>15>;> >res = Collections.binarySearch(al, key);> >if> (res>=>0>)> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >}> }> |
>
>Вихід
10 found at index = 3 15 Not found>
Складність описаного вище способу
Часова складність : O(log N)
Допоміжне приміщення : O(1)