Бинарный поиск php пример

БИНАРНЫЙ ПОИСК PHP

Бинарный поиск является эффективным способом поиска элемента в отсортированном массиве данных. Он работает за логарифмическое время, что делает его оптимальным решением для больших объемов данных.

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

$arr = array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
$left = 0;
$right = count($arr) — 1;
$search = 5;
while ($left $search) <
$right = $middle — 1;
> else <
$left = $middle + 1;
>
>

В данном примере мы ищем значение 5 в отсортированном массиве $arr. Мы сначала определяем начальную и конечную точки поиска ($left и $right соответственно), а затем повторяем процесс до тех пор, пока не найдем искомое значение. Если значение найдено, мы выводим сообщение о том, что элемент найден, и прерываем цикл. В противном случае мы сужаем диапазон поиска, и продолжаем поиск до тех пор, пока не найдем искомое значение, или диапазон поиска не станет равным нулю.

Binary Search — Пишем легендарный Бинарный поиск

Тренировки по алгоритмам от Яндекса. Лекция 6: «Бинарный поиск»

Уроки PHP 7 — Регулярные выражения в PHP

Алгоритм Бинарного поиска (Binary Search) — JavaScript

Пишем логику поиска по сайту — Динамический веб-сайт

Бинарный поиск на PHP — Binary Search Algorithm

Источник

Binary search algorithm in PHP

Binary search is a search algorithm that is dramatically faster than PHP’s internal functions (such as array_search) when searching ordered data.

How does it work?

PHP’s internal function array_search is an example of a linear search; it will iterate over the entire data set until it finds a match working from front to back. This is great if your data set is small and unordered, but is incredibly inefficient when working over large data sets, especially if your match is toward the back of the set, or doesn’t exist at all.

A different approach – divide and conquer

Binary search approaches this problem in a different way. It divides the data set to find the match starting from the middle, to narrow the range that the match can be found within (hence the requirement for your data to be ordered).

A PHP implementation

Below is a PHP example of how to implement a binary search.

function binarySearch($needle, array $haystack, $compare, $high, $low = 0, $containsDuplicates = false) < $key = false; // Whilst we have a range. If not, then that match was not found. while ($high >= $low) < // Find the middle of the range. $mid = (int)floor(($high + $low) / 2); // Compare the middle of the range with the needle. This should return 0 if it's in the second part of the range. It will return 0 if there is a match. $cmp = call_user_func($compare, $needle, $haystack[$mid]); // Adjust the range based on the above logic, so the next loop iteration will use the narrowed range if ($cmp < 0) < $high = $mid - 1; >elseif ($cmp > 0) < $low = $mid + 1; >else < // We've found a match if ($containsDuplicates) < // Find the first item, if there is a possibility our data set contains duplicates by comparing the // previous item with the current item ($mid). while ($mid >0 && call_user_func($compare, $haystack[($mid - 1)], $haystack[$mid]) === 0) < $mid--; >> $key = $mid; break; > > return $key; >

We can utilise this function in the following example by searching an array of email addresses for a specific one. Any test data that appears here was generated by Faker.

$emails = [/* array of emails */]; $searchEmail = '[email protected]'; $key = binarySearch($searchEmail, $emails, 'strcmp', count($emails) - 1, 0, true);

Benchmarks

So let’s benchmark the performance of binary search against PHP’s internal array_search function over a variety of data set sizes and match positions.

Small data set – 100 items

Item exists as the first entry in the data set:

• PHP’s array_search: 0.02599999999997ms
• Binary search: 0.018999999999991ms
• Binary search is 1.37 times faster than array_search

Item exists around the middle of the data set:

• PHP’s array_search: 0.029999999999974ms
• Binary search: 0.020999999999993ms
• Binary search is 1.43 times faster than array_search

Item does not exist in the data set:

• PHP’s array_search: 0.03000000000003ms
• Binary search: 0.019000000000047ms
• Binary search is 1.58 times faster than array_search

Medium data set – 10,000 items

Item exists as the first entry in the data set:

• PHP’s array_search: 0.032000000000032ms
• Binary search: 0.023999999999968ms
• Binary search is 1.33 times faster than array_search

Item exists around the middle of the data set

• PHP’s array_search: 0.12000000000001ms
• Binary search: 0.02000000000002ms
• Binary search is 6 times faster than array_search

Item does not exist in the data set:

• PHP’s array_search: 0.19099999999994ms
• Binary search: 0.021999999999966ms
• Binary search is 8.68 times faster than array_search

Large data set – 1,000,000 items

Item exists as the first entry in the data set:

• PHP’s array_search: 0.037000000000009ms
• Binary search: 0.035000000000007ms
• Binary search is 1.06 times faster than array_search

Item exists around the middle of the data set

• PHP’s array_search: 8.734ms
• Binary search: 0.026000000000082ms
• Binary search is 335.92 times faster than array_search

Item does not exist in the data set:

• PHP’s array_search: 15.676ms
• Binary search: 0.031999999999921ms
• Binary search is 489.87 times faster than array_search

In summary

The results of the benchmarks show that binary search is slightly faster than array_search in most scenarios, but as the data set grows, the performance difference becomes huge. Binary search should be used when you know the data set is large and ordered.

Источник

Русские Блоги

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

В следующем коде массив отсортирован от наименьшего к наибольшему.

 // Определение того, больше ли значение средней позиции, чем значение, которое нужно найти, затем поиск из левой области, начальная позиция остается неизменной, а конечная позиция = средняя позиция -1 if ($arr[$mkey] > $num) < $stop = $mkey - 1; >// Определение того, меньше ли значение средней позиции, чем значение для поиска, затем поиск из правой области, конечная позиция остается неизменной, начальная позиция = средняя позиция + 1 if ($arr[$mkey] < $num) < $start = $mkey + 1; >// Если начальная позиция больше конечной, завершаемся if ($start > $stop) < return false; >return search($arr , $num , $start , $stop); > print_r(search2($arr , $num , 0 , $count));

 // Определение того, больше ли значение средней позиции, чем значение, которое нужно найти, затем поиск из левой области, начальная позиция остается неизменной, а конечная позиция = средняя позиция -1 if ($arr[$mkey] > $num) < $stop = $mkey - 1; >// Определение того, меньше ли значение средней позиции, чем значение для поиска, затем поиск из правой области, конечная позиция остается неизменной, начальная позиция = средняя позиция + 1 if ($arr[$mkey] < $num) < $start = $mkey + 1; >> //Конец return false; > print_r(search2($arr , $num , 0 , $count));

Источник