How would you implement a binary search?

When searching through a list, unless the list is sorted in some fashion, the only sure way to find a given value is to look at every value in the list. But if you are given a sorted list, or if you sort the list before searching, a binary search is a very efficient method to see if a given value is in the list :

method binarySearch(list l, element e):  
if l is empty:    
  return false

let value = l(l.size / 2)
 if (value == e):    
   return true
 if (e < value):    
   return binarySearch(elements between l(0) and l(l.size / 2 - 1)  
else:    
  return binarySearch(elements between l(l.size / 2 + 1) and l(l.size)

The beauty of this algorithm is that you use the property of the sorted list to your advantage. You can throw away many elements without even examining them, because you know they definitely cannot be equal to the given element. If you have a list with one million elements, you can find a given element in as little as twenty comparisons. This algorithm has the performance of O(n). Listing 4-10 shows an implementation of a binary search.

Binary Search

public static boolean binarySearch(final List <Integer> numbers, final Integer value) {
 if (numbers == null || _numbers.isEmpty()) {
  return false;
 }
 final Integer comparison = numbers.get(numbers.size() / 2);
 if (value.equals(comparison)) {
  return true;
 }
 if (value < comparison) {
  return binarySearch(numbers.subList(0, numbers.size() / 2), value);
 } else {
  return binarySearch(numbers.subList(numbers.size() / 2 + 1, numbers.size()), value);
 }
}

core java 12 Algorithm 12

FOLLOW US ON LinkedIn



Explore Tutu'rself