Бинарный поиск алгоритм php

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Поиск значения в массиве с помощью алгоритма «Бинарный поиск» / «Двоичный поиск»

da41b94c/bin-search-php

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

PHP: Алгоритм бинарный поиск

Поиск значения в массиве с помощью алгоритма «Бинарный поиск» / «Двоичный поиск».

Входной массив должен быть отсортирован. Проверка начинается с середины. После каждой проверки исключается половина значений из проверяемого массива.

$sampleList = [ 4, 8, 15, 16, 23, 42 ]; foreach( $sampleList as $val ) < echo binSearch( $sampleList, $val ) .'
'; > // > 0 // > 1 // > 2 // > 3 // > 4 // > 5 echo binSearch( $sampleList, -1 ) .'
'; echo binSearch( $sampleList, 50 ) .'
'; // > не найдено // > не найдено

About

Поиск значения в массиве с помощью алгоритма «Бинарный поиск» / «Двоичный поиск»

Источник

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.

Источник

Binary Search in PHP | Explained with Code Examples

Given a sorted array, write a PHP code to search an element using binary search algorithm.

Output: 3 (6 is found at 3rd index)

Before writing php code, let’s understand what is binary search.

Binary Search

In binary search, first we compute mid by using start and end index. In next step, we compare the value present at mid index to the value k. If search value is found, then the index of the middle element is returned else the algorithm repeats if the value is less than or greater than the middle element.

If the search value is less than or greater than the middle element, than the search continues in the lower or upper half of the array.

The time complexity of binary search is O(logn).

Important points regarding binary search

i) Binary search works only with sorted array.
ii) The time complexity of a binary search is O(logn).

Binary Search in PHP – Code

We have discussed the binary search and it’s algorithm. Let’s write a php code to search an element in an array using binary search.

In this example, I have created one binarySearch method which accepts array and element to be searched in an array. The function return index if the value is found else it return -1.

Источник

An Implementation Of Array Binary Search In PHP

Note: This post is over two years old and so the information contained here might be out of date. If you do spot something please leave a comment and we will endeavour to correct.

I have been doing some reading and watching lectures of programming theory recently and I was reminded of this algorithm I learned about in university. Binary searching an array is a divide and conquer algorithm that takes an array and searches for a value in that array by splitting the array into halves. The algorithm works like this.

• Given a sorted array, find the midpoint.
• If the value at the mid point is greater than the value being searched for then the value must be in the first half of the array.
• If the value at the mid point is less than the value being searched for then the value must be in the first half of the array.
• Take the half of the array in question and repeat the first step by re-pointing the mid point.
• Repeat this until the length of the array is 1 or 0. If the array length is 1 then this is the value. If the length of the array is 0 then the value was not in the array.

There is some implementation details around ensuring that the middle value is correct and to avoid running off the end of the array.

Here is an implementation of the algorithm in PHP.

 elseif ($array[$midpoint] > $value) < // The midpoint value is greater than the value. $right = $midpoint - 1; >else < // This is the key we are looking for. return $midpoint; >> // The value was not found. return NULL; >

To run some tests on this algorithm I ran the following code. All of which prints true.

 $value) < echo var_export(binarySearch($array, $value) === $value, TRUE) . PHP_EOL; >// Search for values outside of the array. echo var_export(binarySearch($array, -1) === NULL, TRUE) . PHP_EOL; echo var_export(binarySearch($array, 11) === NULL, TRUE) . PHP_EOL;

This is a neat little algorithm that is great for searching over arrays of sorted data where the keys of the array are sequential. Much more performant than simply looping through the array to find the value.

Phil is the founder and administrator of #! code and is an IT professional working in the North West of the UK. Graduating in 2003 from Aberystwyth University with an MSc in Computer Science Phil has previously worked as a database administrator, on an IT help desk, systems trainer, web architect, usability consultant, blogger and SEO specialist. Phil has lots of experience building and maintaining PHP websites as well as working with associated technologies like JavaScript, HTML, CSS, XML, Flex, Apache, MySQL and Linux.

Want to know more? Need some help?

Let us help! Hire us to provide training, advice, troubleshooting and more.

Support Us!

Please support us and allow us to continue writing articles.

Источник