Убирать некоторые вещи с дороги
Прежде чем мы сможем перейти к бинарному поиску, мы сначала должны обсудить некоторые ключевые термины и концепции, связанные с программированием / информатикой.
Что такое структура данных?
Структура данных - это конструкция для уникального хранения данных. Структуры данных бывают самых разных форм и размеров. Однако в целом они отдают приоритет возможности максимально эффективно манипулировать данными. Вставка, удаление и поиск данных - одни из наиболее распространенных операций, которые структуры данных пытаются оптимизировать.
Что такое массив?
Массив - это общая структура данных, используемая в программировании. Это массив целых чисел: [12, 16, 17, 19]. Каждому элементу или элементу в массиве соответствует индекс. Массивы обычно имеют нулевую индексацию. Это означает, что начальный индекс массива равен нулю. Если указанный выше массив имеет имя values, тогда values [0] будет 12, values [1] будет 16 и так далее.
Что такое алгоритм?
Алгоритм - это пошаговый процесс, выполнение которого приведет к желаемому результату. Многие популярные алгоритмы в информатике связаны с такими вещами, как поиск, сортировка, сжатие и даже распознавание лиц. Двоичный поиск занимается поиском элемента в отсортированном массиве.
Пора заняться этим!
Вот реальный пример, чтобы понять, как работает бинарный поиск:
- Попросите кого-нибудь угадать число от 1 до 100 (диапазон произвольный, но данные должны быть отсортированы)
- Найдите середину данных
- Если их количество больше среднего, то их количество находится во второй половине данных.
- Если их количество меньше среднего, то их количество находится в первой половине данных.
- Не обращайте внимания на половину данных, где их элемент не находится
- Сосредоточьтесь на половине данных, где находится их элемент
- Повторите этот процесс, начиная со второго маркера, пока не определите их количество.
Теперь, когда у вас есть общее представление о том, как работает этот алгоритм, позвольте мне объяснить его применительно к отсортированному массиву. Вот предыдущий отсортированный массив: [12, 16, 17, 19]. Чтобы выполнить двоичный поиск в отсортированном массиве, нам нужно определить низкий индекс, высокий индекс и средний индекс. Для массива выше низкий индекс равен 0, а высокий индекс равен 3. Средний индекс определяется путем выполнения вычисления: (низкий индекс + высокий индекс) / 2. Выполняемое деление является целочисленным делением. Это означает, что выполнение чего-то вроде 5/2 приведет к 2. Целочисленное деление в программировании отбрасывает дробную часть, которая обычно включается в нормальное деление. Средний индекс для массива выше будет 1. Если значение, расположенное в среднем индексе в массиве, больше, чем значение, которое мы ищем, тогда высокий индекс = средний индекс - 1 (низкий индекс остается неизменным). Если значение, расположенное в среднем индексе в массиве, меньше, чем значение, которое мы ищем, тогда низкий индекс = средний индекс + 1 (высокий индекс остается неизменным). Мы будем продолжать этот процесс до тех пор, пока не найдем искомое значение или пока низкий индекс не станет больше, чем высокий индекс (это означает, что значение не было найдено в массиве).
Что мне лично нравится в этом алгоритме
Бинарный поиск всегда увлекал меня тем, что половина данных удаляется при выполнении одного сравнения. Требование сортировки данных позволяет добиться этого. Когда вы найдете алгоритм, который постоянно избавляется от половины данных, то это, вероятно, алгоритм O (log n). O (log n) - обозначение, связанное с алгоритмической временной сложностью. Я не буду углубляться в временную сложность в этой статье, однако я хочу объяснить ее важность для двоичного поиска. Логарифм в O (log n) относится к двоичному логарифму (логарифму с основанием 2). Двоичный логарифм просто спрашивает: «Какое число я могу возвести до основания 2, чтобы получить желаемый результат?» Например, log (8) = 3 (с двоичным логарифмом), потому что вам нужно возвести 3 в основание 2, чтобы получить 8. Как вся эта чушь связана с двоичным поиском? Если у нас есть 500 значений для поиска, то двоичный поиск гарантирует, что мы найдем наше значение в пределах log (500) попыток (log (500) приблизительно равен 9 при округлении до ближайшего целого числа). Вот почему говорят, что алгоритм работает за время O (log n). Самая крутая часть - сказать людям, что вы можете угадать число, которое они придумали, после стольких попыток. Если вы попросили кого-нибудь угадать число от 1 до 100, то вы могли бы с уверенностью сказать ему, что угадаете его число за 7 попыток! В этом прелесть бинарного поиска.
