Модели и структуры данных

Двоичный поиск в упорядоченном массиве

• 1

• 2

• 3

• 4

• 5

• 6

• 7

• 8

• 9

• 10

• 11

• 12

• 13

• 14

• 15

• 16

• 17

• 18

• 19

• 0

• 1

• 3

• 4

• 8

• 10

• 14

• 16

• 21

• 24

• 27

• 31

• 33

• 36

• 38

• 42

• 44

• 50

• 51

• 53

• 59

• l

• h

• m

• 33

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

• using System;
• class Program{
• //метод для рекурсивного бинарного поиска
• static int BinarySearch(int[] array, int searchedValue, int first, int last){
• //границы сошлись
• if (first > last){
• //элемент не найден
• return -1;
• }
• //средний индекс подмассива
• var middle = (first + last) / 2;
• //значение в средине подмассива
• var middleValue = array[middle];

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

• if (middleValue == searchedValue)
• { return middle; }
• else {
• if (middleValue > searchedValue) {
• //рекурсивный вызов поиска для левого
• подмассива
• return BinarySearch(array,
• searchedValue, first, middle - 1);
• } else {
• //рекурсивный вызов поиска для правого подмассива
• return BinarySearch(array, searchedValue, middle + 1, last);
• }
• }
• }

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

• //программа для бинарного поиска элемента в упорядоченном массиве
• static void Main(string[] args){
• Console.WriteLine("Бинарный поиск (рекурсивная реализация)");
• Console.Write("Введите элементы массива: ");
• var s;
• s=Console.ReadLine().Split(new[] {" ",",", ";"}, StringSplitOptions.RemoveEmptyEntries);
• var array = new int[s.Length];
• for (int i = 0; i < s.Length; i++){
• array[i] = Convert.ToInt32(s[i]);
• }

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

• //сортируем массив
• Array.Sort(array);
• Console.WriteLine("Упорядоченный массив: {0}", string.Join(", ", array));
• while (true){
• Console.Write("Введите искомое значение или -777 для выхода: ");
• var k = Convert.ToInt32(Console. ReadLine());
• if (k == -777){ break; }
• var searchResult = BinarySearch(array, k, 0, array.Length - 1);

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

• if (searchResult < 0){
• Console.WriteLine("Элемент со значением {0} не найден", k);
• } else{
• Console.WriteLine("Элемент найден. Индекс элемента со значением {0} равен {1}", k, searchResult);
• }
• }
• Console.ReadLine();
• }
• }

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

• //метод бинарного поиска с использованием цикла
• static int BinarySearch(int[] array, int searchedValue, int left, int right)
• { //пока не сошлись границы массива
• while (left <= right)
• { //индекс среднего элемента
• var middle = (left + right) / 2;
• if (searchedValue == array[middle])
• { return middle;
• }
• else if (searchedValue < array[middle])
• {

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

• //сужаем рабочую зону массива с правой стороны
• right = middle - 1;
• }
• else
• {
• //сужаем рабочую зону массива с левой стороны
• left = middle + 1;
• }
• }
• //ничего не нашли
• return -1;
• }

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

• скорость выше, чем при линейном поиске

• нужна предварительная сортировка

• Когда нужно применять?

• ?

• Число сравнений:

Задачи

• «A»: Заполнить массив случайными числами и отсортировать его. Ввести число X. Используя двоичный поиск, определить, есть ли в массиве число, равное X. Подсчитать количество сравнений.
• Пример:
• Массив:
• 1 4 7 3 9 2 4 5 2
• После сортировки:
• 1 2 2 3 4 4 5 7 9
• Введите число X:
• 2
• Число 2 найдено.
• Количество сравнений: 2

Задачи

• «B»: Заполнить массив случайными числами и отсортировать его. Ввести число X. Используя двоичный поиск, определить, сколько чисел, равных X, находится в массиве.
• Пример:
• Массив:
• 1 4 7 3 9 2 4 5 2
• После сортировки:
• 1 2 2 3 4 4 5 7 9
• Введите число X:
• 4
• Число 4 встречается 2 раз(а).
• Пример:
• Массив:
• 1 4 7 3 9 2 4 5 2
• После сортировки:
• 1 2 2 3 4 4 5 7 9
• Введите число X:
• 14
• Число 14 не встречается.

Задачи

• «C»: Заполнить массив случайными числами и ввести число и отсортировать его. Ввести число X. Используя двоичный поиск, определить, есть ли в массиве число, равное X. Если такого числа нет, вывести число, ближайшее к X.
• Пример:
• Массив:
• 1 4 7 3 9 2 4 5 2
• После сортировки:
• 1 2 2 3 4 4 5 12 19
• Введите число X:
• 12
• Число 12 найдено.
• Пример:
• Массив:
• 1 4 7 3 9 2 4 5 2
• После сортировки:
• 1 2 2 3 4 4 5 12 19
• Введите число X:
• 11
• Число 11 не найдено. Ближайшее число 12.