В мире программирования поиск — обычная проблема. Ищете ли вы элемент в массиве, номер телефона в телефонной книге или пытаетесь найти конкретное значение в базе данных, поиск является распространенным методом, который используется при разработке программного обеспечения.

Одним из известных алгоритмических методов поиска является бинарный поиск. Двоичный поиск — это алгоритмический метод поиска для поиска позиции значения в отсортированном списке или массиве. он имеет временную сложность O (log ^ n), что означает, что его производительность улучшается по мере роста размера набора данных.

Здесь мы обсудим основы бинарного поиска и принципы его работы, а затем перейдем к реализации бинарного поиска в JavaScript.

Прежде чем мы начнем, есть некоторые предпосылки для бинарного поиска.

1. Бинарный поиск работает только в отсортированном списке или массиве. Если ваши данные не отсортированы, вам необходимо отсортировать данные перед использованием бинарного поиска.

2. Иметь некоторое представление о нотации Big O. Это поможет проанализировать производительность бинарного поиска.

3. Хорошо разбираться в языках программирования.

Как работает бинарный поиск:

Бинарный поиск работает по правилу «разделяй и властвуй». Деление означает, что бинарный поиск делит отсортированный массив или список на 2 и сравнивает целевое значение со средним значением. Если целевое значение больше среднего значения, поиск будет производиться в левом массиве.

Давайте посмотрим шаг за шагом:

1. Начните с отсортированного списка или массива значений.

2. Определите средний элемент списка или массива.

3. Если средний элемент равен целевому значению, вернуть его индекс.

4. Если средний элемент больше целевого значения, выполните поиск в левой половине списка или массива (т. е. в элементах перед средним элементом).

5. Если средний элемент меньше целевого значения, выполните поиск в правой половине списка или массива (т. е. элементы после среднего элемента).

6. Повторяйте шаги 2–5 для выбранной половины списка или массива, пока целевое значение не будет найдено или определено как отсутствующее.

Ключевое различие между бинарным и линейным поиском заключается в том, что бинарный поиск удаляет половину оставшегося списка или массива на каждой итерации, что приводит к временной сложности O (log n), а не O (n) для линейного поиска. По сравнению с линейным поиском бинарный поиск намного быстрее для больших наборов данных.

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

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

// Binary Search or You can Say Divided and conquer
const arrOfNum = [ 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140 ]

const key = 110;

function binarySearch (arr , key) {
    let start = 0;
    let end = arr.length - 1;
    
 while (start <= end){
    // At each iteration, the function computes the middle index mid using the formula (start + end) / 
    // 2 and checks if the element at mid is equal to the target value key. If so, the function returns mid. If not, the function updates either 
    // the start or end index depending on whether the element at mid is less than or greater than key.
    let mid = Math.floor((start + end ) /2)
    if(arr[mid] === key){
        return `${key} found at ${mid} index In array`;
    }else if(arr[mid] < key ){
        start = mid + 1;
    } else{
        end = mid - 1;
    }
 }
//  The while loop continues until either the key is found 
// or start becomes greater than end. If the key is not found, the function returns 
 return `${key} Not found in Array` ;
}
// `70 found at 6 index In array`
console.log(binarySearch(arrOfNum , key));

Здесь массив чисел с именем arrOfNum и ключ переменной, который представляет значение, которое мы ищем в массиве.

Функция binarySearch принимает два параметра: массив для поиска и ключ для поиска.

Внутри функции две переменные start и end инициализируются соответственно первым и последним индексами массива.

Затем функция входит в цикл while, который продолжается до тех пор, пока start не станет больше end. На каждой итерации цикла функция вычисляет средний индекс середины массива, используя формулу (начало + конец)/2, и сравнивает значение элемента по этому индексу с ключом.

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

Если элемент в середине меньше ключа, функция обновляется до середины + 1, чтобы можно было продолжить поиск в верхней половине массива.

Если элемент в середине больше ключа, функция обновляет конец до середины — 1, чтобы можно было продолжить поиск в нижней половине массива.

Если цикл завершается, а ключ не найден, функция возвращает строку, указывающую, что ключ не найден в массиве.

В этой реализации функция Math.floor() используется для проверки того, что mid является целым числом, поскольку деление двух целых чисел в JavaScript может привести к нецелочисленному значению.

Наконец, бинарный поиск — эффективный алгоритм поиска в отсортированных массивах. Он имеет временную сложность O(log n), что делает его значительно быстрее, чем линейный поиск больших массивов.

В этом подробном руководстве мы рассмотрели основы бинарного поиска, в том числе то, как он работает.

Всегда помните, что практика делает совершенным! Чем больше вы используете бинарный поиск, как и любую другую концепцию программирования, тем комфортнее и опытнее вы становитесь. Итак, продолжайте кодировать и искать!