Двоичный поиск в массиве (C++)

• Двоичный (бинарный) поиск — метод поиск элементов в отсортированном массиве путём деления его на две части.

 

• Пример. Найдём индекс ячейки, в которой хранится число 4.

  Решение.

• ищем средний элемент при деления массива на 2 части $(0 + 11) / 2 = 5$(округление вниз). Элемент с индексом 5 больше искомого числа. Следовательно, проверяем первую половину массива;

• ищем средний элемент первой половины массива $(0 + 4) / 2 = 2$. Элемент с индексом 2 меньше искомого числа. Следовательно, рассматриваем вторую половину массива;

• ищем средний элемент второй половины массива $(3 + 4) / 2 = 3$. Элемент с индексом 3 равен искомому элементу.

• Ответ. Число 4 хранится в ячейке с индексом 3.