What is the binary search in an ordered list?

Half search in an ordered list: take the middle value as the comparison object. If the given value is equal to the key of the middle value, the search is successful; if the given value is less than the key of the middle record, then the search is successful. The search continues in the left half of the middle record.

#The operating environment of this article: Windows 7 system, Dell G3 computer.

Half search concept:

Half search, also known as binary search.

The premise is that the records in the linear table must be in key order (from small to large or from large to small), and the linear table must be stored sequentially.

The basic idea of ​​half search is: In an ordered list, take the middle value as the comparison object. If the given value and the key of the middle value are equal, the search is successful; if If the given value is less than the key of the middle record, the search will continue in the left half of the middle record; if the given value is greater than the key of the middle record, the search will continue in the right half of the middle record. Repeat the above process until the search is successful, or there is no record in all areas and the search fails.

Algorithm implementation:

public int Binary_Search(int[] a, int n, int key) {
int low = 1, high = n, mid;
while(low <= high) {
mid = (int)((low + high) / 2);
if(key < a[mid]) {
high = mid - 1;
}
else if(key > a[mid]) {
low = mid + 1;
}
else return mid;
}
return 0;
}

Usually three pointers low, high, and mid are used. Respectively represent the leftmost value subscript of the search area, the rightmost value subscript of the search area, and the current comparison value subscript.

Time complexity analysis:

Half search is actually equivalent to dividing the static ordered lookup table into two subtrees, that is, only half of the data needs to be found during the search. That’s it, which means the workload is reduced by half to improve efficiency.

Related video recommendations: PHP programming from entry to proficiency

The above is the detailed content of What is the binary search in an ordered list?. For more information, please follow other related articles on the PHP Chinese website!