Автор оригинала: Abhay Chaturvedi.
Бинарный поиск-один из самых распространенных способов поиска по любому отсортированному списку.
Она основана на том, как наш мозг решает эту проблему интуитивно. Просто рассмотрим следующий псевдокод:
BinarySearch(Arr,value,low,high): if (highvalue) return BinarySearch(Arr,value,low,mid-1) return mid
Разве это не похоже на то, как мы ищем такие вещи, как наш регистрационный номер в списке регистрации для определенного класса?
- Мы смотрим на первый номер рулона и последний номер.
- Затем мы сужаем окно поиска до тех пор, пока не достигнем места, где (скорее всего) будет находиться наш номер броска.
Это довольно короткий ускоренный курс по применению бинарного поиска. Однако знаете ли вы, что этот подход также может быть применен к решению уравнений? Теперь это звучит и весело, и это именно то, что мы собираемся исследовать дальше.
За пределами Массивов
Это случилось в прошлом году. У меня была конкретная проблема в моей работе по гидрологии, которая требовала от меня найти приблизительное решение:
- x log(x) +
- или x log(x) + x -. Все, что у меня было, – это калькулятор, который мог делать логарифмы. Итак, вот мой подход:
- Проверьте и число, где функция имеет знак, противоположный(здесь говорят)
- инициализировать и.Теперь результат должен лежать в интервале (низкий,высокий)
- Начните петлю, где для каждого поворота:
- mid = (high+low)/2
- if(abs(x log(x)+x-6000)<0.2) #for x then break
- иначе обновите high и low с помощью mid так, чтобы знак функции у них был противоположным. Я смог получить погрешность в 10 в течение 6 шагов вычислений с помощью моего калькулятора.
Ниже приведен код python для этого подхода.
from math import log def myFunc(x): return 1000*log(x) + (x) - 6000 low = 1 high = 1000 mid = (high+low)/2 while(abs(myFunc(mid))>0.2): print mid,myFunc(mid) if myFunc(mid)*myFunc(high)>0: low,high = low,mid else: low,high = mid,high mid = (high+low)/2.0 print mid,myFunc(mid)
И его выход:
500 714.608098422 250.5 -226.041079475 375.25 302.842470514 312.875 58.6787497519 281.6875 -77.5141995491 297.28125 -8.04008959327 305.078125 25.6460163482 301.1796875 8.88674257264 299.23046875 0.444543723073 298.255859375 -3.79243398916 298.743164062 -1.67261475274 298.986816406 -0.613703461946 299.108642578 -0.0844969238451
Как вы можете ясно видеть, мы достигли приемлемого решения в течение 13 шагов.
Вывод
Из приведенного выше процесса мы можем сделать вывод, что двоичный поиск-это интуитивно понятный алгоритм, использование которого не должно ограничиваться только поиском по массивам. Используя описанный выше подход, можно решить множество простых уравнений — логарифмических, экспоненциальных и полиномиальных.
С другой философской точки зрения, реальная числовая строка-это не что иное, как сортированный массив, и каждая задача решения уравнения, таким образом, аналогична задаче поиска. Поскольку бинарный поиск является отличным алгоритмом поиска, мы можем использовать его для всех подобных задач. И это, друзья мои, был мой взгляд на алгоритм Бинарного поиска.
Я всегда готов ответить на любые ваши вопросы в Abhay447 !