Краткий обзор того, как работает бинарный поиск

Существует так много способов поиска по списку элементов, что двоичный поиск - один из наиболее эффективных методов.

Этот метод работает только для отсортированного списка, поэтому приоритет номер один - убедиться, что ваш список отсортирован (если нет, отсортируйте его самостоятельно).

Что делает бинарный поиск, так это разделение списка пополам и проверка того, больше ли целевой элемент среднего или меньше.

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

Этот блог предназначен просто для понимания того, как писать двоичный поиск.

Код:

function binarySearch(sortedArr, target) {
  let startPoint = 0 // Index of the first element in the array
  let endPoint = sortedArr.length - 1 // Index of the last element
  while (startPoint <= endPoint) {
    let midPoint = Math.floor((startPoint + endPoint) / 2)
    // Getting the halfway point of the start and end points, must be an integer so we use Math.floor()
    if (sortedArr[midPoint] < target) {
      startPoint = midPoint + 1
    } 
    // Ignore the half of the list that definitely will not contain     the target since all the items are less than the target
    // Set new startPoint to one integer above midPoint
else if (sortedArr[midPoint] > target) {
      endPoint = midPoint - 1
    } 
    // Ignore the half of the list that definitely will not contain the target since all items are greater than the target
    // Set new endPoint to one integer below midPoint
  
    else {
      return midPoint
    } 
    // midPoint is now equivalent to target, target has been found!
  }
  return "Target Not Found"
  // While loop has completed yet the midPoint was never equivalent to target, therefore the target does not exist in the sorted array.
}

Заключение

Вот и все! Как новичок в программировании, я считаю, что важнее сначала понять, как использовать определенные методы, прежде чем начинать погружаться в то, как это работает «изнутри».

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

Представьте, что вам нужно просмотреть весь список и по очереди проверять, соответствует ли элемент цели. Если бы в списке было больше сотни пунктов, это заняло бы вечность!

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