Java™ How To Program (Early Objects), Tenth Edition

Section 19.4 Binary Search

• Binary search (p. 816) is more efficient than linear search, but it requires that the array be sorted.

• The first iteration of binary search tests the middle element in the array. If this is the search key, the algorithm returns its location. If the search key is less than the middle element, the search continues with the first half of the array. If the search key is greater than the middle element, the search continues with the second half of the array. Each iteration tests the middle value of the remaining array and, if the element is not found, eliminates half of the remaining elements.

• Binary search is a more efficient searching algorithm than linear search because each comparison eliminates from consideration ...