Home > Common Problem > What is the binary search in an ordered list?

What is the binary search in an ordered list?

coldplay.xixi
Release: 2023-01-13 00:30:36
Original
5558 people have browsed it

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.

What is the binary search in an ordered list?

#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;
}
Copy after login

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!

Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template