Бинарный поиск: За пределами Массивов

Бинарный поиск-один из самых распространенных способов поиска по любому отсортированному списку.

Она основана на том, как наш мозг решает эту проблему интуитивно. Просто рассмотрим следующий псевдокод:

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 !