In computer science, a binary search is an algorithm for locating the position of an element in a sorted list by checking the middle, eliminating half of the list from consideration, and then performing the search on the remaining half. If the middle element is equal to the sought value, then the position has been found; otherwise, the upper half or lower half is chosen for search based on whether the element is greater than or less than the midd...
more
In computer science, a binary search is an algorithm for locating the position of an element in a sorted list by checking the middle, eliminating half of the list from consideration, and then performing the search on the remaining half. If the middle element is equal to the sought value, then the position has been found; otherwise, the upper half or lower half is chosen for search based on whether the element is greater than or less than the middle element. The method reduces the number of elements needed to be checked by a factor of two each time, and finds the target value, if it exists in logarithmic time. A binary search is a dichotomic divide and conquer search algorithm.
Viewing the comparison as a subtraction of the sought element from the middle element, only the sign of the difference is inspected: there is no attempt at an interpolation search based on the size of the difference.
Finding the index of a specific value in a sorted list is useful because, given the index, other...
less
