Шаг 2.
Алгоритмы.
Бинарный поиск. Программная реализация

    На этом шаге рассмотрим программную реализацию алгоритма бинарного поиска.

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

    Посмотрим, как написать реализацию бинарного поиска на C++. В следующем примере кода используется массив (серия однотипных элементов, сохраненных в непрерывной последовательности ячеек). Нумерация ячеек начинается с нуля: первая ячейка находится в позиции с номером 0, вторая - в позиции с номером 1 и т. д.

    Функция bin_search получает отсортированный массив, загаданное число и количество элементов в массиве. Если значение присутствует в массиве, то функция возвращает его позицию, иначе функция вернет значение -1. Пример работы функции представлен на рис. 1.


Рис.1. Пример работы функции bin_search

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

    Каждый раз алгоритм проверяет средний элемент:

    Код функции bin_search выглядит так:

int bin_search(int mas[], int n, int p)
{
  /*  В переменных low и high хранятся границы той части списка,
      в которой выполняется поиск  */
	int low = 0, high = p - 1;
       /* Пока эта часть не сократиться до одного элемента....  */
        while(low <= high)
	{
                 /*  вычисляем позицию среднего элемента   */
                int mid = (low + high) / 2;
		/* Значение найдено  */
                if(mas[mid] == n) return mid;
               	/* Значение больше загаданного  */
                if(mas[mid] > n) high = mid - 1;
                /* Значение меньше загаданного  */
		else low = mid + 1;
	}
	/* Такого значения нет  */
	return -1;
}

    На следующем шаге рассмотрим применение алгоритма бинарного поиска при решении конкретных задач.




Предыдущий шаг Содержание Следующий шаг