Программа двоичного поиска Java | Двоичный поиск в примере Java

Мы собираемся узнать об одном из самых быстрых методов поиска, которым является двоичный поиск. Этот метод поиска также известен как поиск с половинным интервалом, поиск по логарифму или двоичное чередование. Всегда помните, что этот метод поиска работает только в отсортированном массиве или list . Бинарный поиск используется для поиска ключевого элемента из нескольких элементов. Двоичный поиск быстрее, чем линейный поиск.

Двоичный поиск Java

В случае двоичного поиска элементы массива должны быть в порядке возрастания. Если у вас есть несортированный массив, вы можете отсортировать его, используя метод Arrays.sort (arr) .

Двоичный поиск работает следующим образом.

Поиск в отсортированном массиве путем многократного деления интервала поиска пополам.

Начните с интервала, охватывающего весь массив.

Если значение ключа поиска меньше элемента в середине интервала, сузьте интервал до нижней половины.

В противном случае сузьте его до верхней половины. Неоднократно проверяйте, пока значение не будет найдено или интервал не станет пустым.

#Procedure

Стандартная процедура этого поиска: сначала мы должны взять отсортированный массив, а затем мы должны сравнить целевое значение со средним значением отсортированного массива.

Если целевое значение меньше среднего значения, тогда мы удалим оставшиеся половины (правая часть среднего значения) и продолжим поиск с выбранными половинами.

Затем мы снова возьмем среднее значение выбранных половинок (левый подмассив) и сравним, снова мы должны исключить путем сравнения, и мы будем делать это, пока не получим целевое значение.

# Алгоритм двоичного поиска

 1.  [Определить переменные] ST = LB, LAST = UB; //LB означает нижнюю границу, UB = верхнюю границу MID = (ST + LAST)/2; //Среднее значение 2.  Повторите 3 и 4 DO ST  

# Объяснение на примере

Предположим, что это отсортированный массив.

Значение 12 15 17 29 31 41 55
Индекс 0 1 2 3 4 5 6

Теперь предположим, что наше целевое значение T = 17, которое находится в индексе 2. Мы увидим, как в этом случае будет применяться двоичный поиск.

LB = 0 и UB = 6, поэтому среднее значение будет: MID = (0 + 6)/2 = 3, поэтому наше среднее значение находится в позиции LOC = 3.

Pass1: Теперь мы сравним целевое значение (T) со средним значением (MID), поскольку мы видим T

Pass2: Теперь нашим средним значением будет индекс 1 и целевое значение T = 17, как есть. Теперь мы сравним MID с T, так как T> MID, чтобы исключить левый подмассив.

Pass3: Теперь наше среднее значение и единственное оставшееся значение — с индексом 2, то есть 17. Кроме того, мы можем видеть, что наше целевое значение T также равно 17. Итак, после сравнения, когда мы получим это MID == T, мы остановимся и вернем местоположение целевого значения, которое является LOC = 2 .

Итак, из примера мы можем сказать, что наше целевое значение присутствует в позиции индекса.

# Программа двоичного поиска в Java

См. программу ниже.

 import java.util. *; class Binary {  public static void main (String args []) {Scanner sc = new Scanner (System.in);  System.out.println (" nВведите длину массива:");  int len ​​= sc.nextInt ();  int [] arr = новый int [len];  System.out.println ("Введите элементы массива:  n");  для (int я = 0; я  = 0) System.out.println ("Целевое значение находится в индексе:" + loc);  else System.out.println («Целевое значение не найдено»);  } public static int BinarySearch (int arr [], int LB, int UB, int data) {int mid = (LB + UB)/2;  int loc = -1;  while ((LB  

См. вывод ниже.

# Временная сложность

Временную сложность двоичного поиска мы можем записать следующим образом.

 T (n  ) = T (n/2) + c 

Вышеупомянутое повторение может быть решено либо с помощью метода дерева повторения, либо метода мастера.

Он выпадает в случае II Мастер-метода, и решение повторения будет следующим.

 Theta (log n) 

# Сложность пространства

O (1) в случае итеративной реализации. В случае рекурсивной реализации.

O (log n) пространство стека вызовов рекурсии.

Наконец, программа двоичного поиска Java завершена.

Оцените статью
nanomode.ru
Добавить комментарий