Статьи

Бинарный поиск в Java без рекурсии — итерационный алгоритм

Январь 1, 2019

Задача этой недели — реализовать бинарный поиск в Java, вам нужно написать итеративный и рекурсивный алгоритм бинарного поиска . В информатике бинарный поиск или полуинтервальный поиск — это алгоритм «разделяй и властвуй», который определяет положение элемента в отсортированном массиве. Бинарный поиск работает путем сравнения входного значения со средним элементом массива. Сравнение определяет, равен ли элемент входу, меньше, чем вход или больше. Когда сравниваемый элемент равен входным данным, поиск останавливается и обычно возвращает позицию элемента. Если элемент не равен входному значению, выполняется сравнение для определения того, является ли входное значение меньшим или большим, чем элемент. В зависимости от того, какой именно алгоритм затем запускается заново, он ищет только верхнее или нижнее подмножество элементов массива. Если входные данные не находятся в массиве, алгоритм обычно выводит уникальное значение, указывающее это.

Алгоритмы бинарного поиска обычно делят вдвое меньше элементов, которые нужно проверять при каждой последующей итерации, тем самым находя данный элемент (или определяя его отсутствие) в логарифмическом времени. Бинарный поиск — это алгоритм поиска «разделяй и властвуй». Он работает, деля входной набор на половину, а затем применяя алгоритм и повторяя те же шаги, пока работа не будет завершена.

Бинарный поиск

Реализация бинарного поиска в Java

Алгоритм реализован рекурсивно. Кроме того, интересный факт о реализации бинарного поиска в Java заключается в том, что Джошуа Блох, автор знаменитого
Эффективная книга Java написала бинарный поиск в «java.util.Arrays».

1
2
import java.util.Arrays;
import java.util.Scanner;
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/**
* Java program to implement Binary Search. We have implemented Iterative
* version of Binary Search Algorithm in Java
*
* @author Javin Paul
*/
public class IterativeBinarySearch {
 
    public static void main(String args[]) {
 
        int[] list = new int[]{23, 43, 31, 12};
        int number = 12;
        Arrays.sort(list);
        System.out.printf("Binary Search %d in integer array %s %n", number,
                           Arrays.toString(list));
        binarySearch(list, 12);
 
        System.out.printf("Binary Search %d in integer array %s %n", 43,
                           Arrays.toString(list));
        binarySearch(list, 43);
 
        list = new int[]{123, 243, 331, 1298};
        number = 331;
        Arrays.sort(list);
        System.out.printf("Binary Search %d in integer array %s %n", number,
                           Arrays.toString(list));
        binarySearch(list, 331);
 
        System.out.printf("Binary Search %d in integer array %s %n", 331,
                           Arrays.toString(list));
        binarySearch(list, 1333);
 
        // Using Core Java API and Collection framework
        // Precondition to the Arrays.binarySearch
        Arrays.sort(list);
 
        // Search an element
        int index = Arrays.binarySearch(list, 3);
 
    }
 
    /**
     * Perform a binary Search in Sorted Array in Java
     *
     * @param input
     * @param number
     * @return location of element in array
     */
    public static void binarySearch(int[] input, int number) {
        int first = 0;
        int last = input.length - 1;
        int middle = (first + last) / 2;
 
        while (first <= last) {
            if (input[middle] < number) {
                first = middle + 1;
            } else if (input[middle] == number) {
                System.out.printf(number + " found at location %d %n", middle);
                break;
            } else {
                last = middle - 1;
            }
            middle = (first + last) / 2;
        }
        if (first > last) {
            System.out.println(number + " is not present in the list.\n");
        }
    }
}
 
 
Output
Binary Search 12 in integer array [12, 23, 31, 43]
12 found at location 0
Binary Search 43 in integer array [12, 23, 31, 43]
43 found at location 3
Binary Search 331 in integer array [123, 243, 331, 1298]
331 found at location 2
Binary Search 331 in integer array [123, 243, 331, 1298]
1333 is not present in the list.

Это все о том, как реализовать итеративный двоичный поиск в Java.

Спасибо за чтение этой статьи до сих пор. Если вам понравилась эта статья, пожалуйста, поделитесь с друзьями и коллегами. Если у вас есть какие-либо вопросы или пожелания, напишите нам.

См. Оригинальную статью здесь: бинарный поиск в Java без рекурсии — итерационный алгоритм

Мнения, высказанные участниками Java Code Geeks, являются их собственными.

70
Share: