A brief discussion on PHP Part 3---Using binary search method to find the position of elements in an array

A brief discussion on PHP Part 3---Using binary search method to find the position of elements in an array_PHP Tutorial

WBOY

Release： 2016-07-13 17:50:14

Original

1002 people have browsed it

In php, we can use the array_search() function to find the key name of the element value in an array.

Similarly, we can find the key names of elements in the array by using the binary method.
So what is dichotomy?

Let me explain:
If the data is sorted in ascending order, we start searching from the middle position of the data. If the given value is exactly equal to the value of the current position, the search is successful. If the given value is less than the value of the current position, then we start from the current value. Search for the first half of the value based on the current value. On the contrary, if the given value is greater than the current value, then search for the second half of the value based on the current value.

In other words, the data searched using the binary method must be sorted.
Next we try to find the position of a value in the array (1,2,3,4,5,6,7,8,9,10):
function Search($a,$val){
$low = 0;
$high= count($a) - 1;
while($low <= $high){
$mid = intval(($low+$high)/2);
if($a[$mid] == $val)
return $mid;
if($a[$mid] > $val){
$high = $mid - 1;
}else{
$low = $mid + 1;
}
}
return -1;
}
?>
For the above function, the first parameter is the incoming array, and the second parameter is the value to be queried in the array.
We set a minimum value of $low for the key of the array to 0, and set a maximum value of $high to the length of the array minus one. Then we can set the intermediate value to intval(($low+$height)/2),
That is to say, when the length of the array elements is an odd number, the middle value of the array is exactly in the middle,
For example, if the array length is 5, then the middle value is exactly 2, which is (0+4)/2,
0,1,2,3,4
When the length of our array is an even number, it cannot be divided using the above formula, so we have to round, whether it is rounding by the addition method or the rounding method
For example, if the array length is 6, then the middle value is (0+5)/2, and the value is 2.5, then the key in the array is 2.5 does not exist, so we need to round to 2
0,1,2,3,4,5
If you use the above rounding function intval or floor function, the key obtained is 2. If you use ceil rounding, the key obtained here is 3

So, let’s take the above array as an example:
The length of the array is 10, then the intermediate value is intval((0+(10-1))/2), which is 4, and the index of 4 is the fifth element "5"
in the array 1,2,3,4,5,6,7,8,9,10

Okay, let’s start judging next,
1. If the value to be queried happens to be "5", the search is successful and the index of the value can be returned directly.
That is
if($a[$mid] == $val)
return $mid;
2. If the value to be queried is less than "5", we need to set the value of $high to the middle value minus one, which is 4-1, and return to the first half (red part) of the middle value to continue querying
1,2,3,4,5,6,7,8,9,10
That is:
if($a[$mid] > $val){
$high = $mid - 1;
}

3. If the value to be queried is greater than "5", we need to set the value of $low to the middle value plus one, which is 4+1, and return to continue to query the second half of the middle value (red part)
1,2,3,4,5,6,7,8,9,10
That is:
else{
$low = $mid + 1;
}
After setting, return and continue querying. If the condition $low<=$high is met, the query will be repeated until this condition is not true, that is, when the range being queried is less than one array element, it will be said that the value to be queried does not exist in the array. Return -1
while($low <= $high){
.......
}
return -1;
The disadvantages of this function are:
If there are duplicate values in the array, only the key of one of the values can be found. If you are interested, you can improve the above function and leave a reply.

Excerpted from zdrjlamp