Hash Tables: Ice Cream Parlor
Binary Search
Concept
This is a very efficient way to find data in a sorted dataset. Binary Search is a recursive algorithm that works by partitioning the dataset in half and then evaluating whether the desired value will fall in the lower half or the upper half of the dataset. You then simply continue to recursively search whichever half the desired value would be located in until such a time as you either find the desired value in the dataset or the dataset can no longer be halved.
Because we're discarding half of the dataset at each step, we go from having possible indices to to and so on until we get down to the last possible index. If the value isn't found at that index, then we know it's not in the array. The number of times we can divide by until we get down to the last possible index where the value might be found is .
Reference: Algorithms Sequential and Parallel: A Unified Approach
Asymptotic Analysis
- Worst Case:
- Best Case:
- Average Case:
Basic Algorithm
Iterative
// Initialize search bounds to the length of the array
int left = 0;
int right = array.length - 1;
// If the only possible location of the value is outside of the current search bounds, it doesn't exist in the array
while(left <= right) {
// Calculate a middle value
int mid = left + (right - left) / 2;
// If the search value is found at the middle of the current search range
if(array[mid] == searchValue) {
return true;
}
// If the search value would fall in the left half of the dataset (i.e., less than middle), search left
else if(searchValue < array[mid]) {
right = mid - 1;
}
// Else, the search value can only fall in the right half of the dataset (i.e., greater than middle), search right
else {
// search right
left = mid + 1;
}
}
// This is only reached if the search value was never found
return false;
Recursive
// If the only possible location of the value is outside of the current search bounds, it doesn't exist in the array
if(left > right) {
return false;
}
// Calculate a middle value
mid = left + ((right - left) / 2);
// If the search value is found at the middle of the current search range
if(array[mid] == searchValue) {
return true;
}
// If the search value would fall in the left half of the dataset (i.e., less than middle)
else if(searchValue < array[mid]) {
seach from left to mid - 1
}
// Else, the search value can only fall in the right half of the dataset (i.e., greater than middle)
else {
search from mid + 1 to right
}
// This is only reached if the search value was never found
return false;
Example (Java)
Input Format
The first line contains a single integer, , denoting the number of elements in the array. The array will fill with distinct integers from to .
The second line contains some number of space-separated integers denoting values to search the array for.
import java.util.*;
class BinarySearch<E extends Comparable<E>> {
E[] array;
public BinarySearch(E[] array) {
this.array = array;
}
/** Recursive Binary Search - Helper Method **/
public void findRecursive(E value) {
int index = binarySearchRecursive(value, -1, 0, array.length - 1);
System.out.println(
(index > -1)
? "Value '" + value + "' was found recursively at index: " + index
: "Value '" + value + "' was not found recursively in the dataset: " + Arrays.asList(array)
);
}
/** Recursive Binary Search Implementation **/
private int binarySearchRecursive(E value, int index, int left, int right) {
if(left <= right) {
int midIndex = left + ((right - left) / 2);
// If value is found
if(value.equals(array[midIndex])) {
index = midIndex;
}
else {
// if value < array[midIndex], search left
if(value.compareTo(array[midIndex]) < 0) {
right = midIndex - 1;
}
else { // if value > array[midIndex], search right
left = midIndex + 1;
}
index = binarySearchRecursive(value, index, left, right);
}
}
return index;
}
/** Iterative Binary Search Implementation **/
public void findIterative(E value) {
// Initial values
int left = 0;
int right = array.length - 1;
int index = -1;
// While there is a section having length > 0 to search
while(left <= right && index < 0) {
int mid = left + ((right - left) / 2);
// If value is found
if(array[mid] == value) {
index = mid;
break;
}
// If value < array[mid], search left
else if(value.compareTo(array[mid]) < 0) {
// search left
right = mid - 1;
}
else { // If value > array[mid], search right
left = mid + 1;
}
}
System.out.println(
(index > -1)
? "Value '" + value + "' was found iteratively at index: " + index
: "Value '" + value + "' was not found iteratively in the dataset: " + Arrays.asList(array)
);
}
public void search(E value) {
findRecursive(value);
findIterative(value);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// Size of dataset
int n = scanner.nextInt();
// Create sorted dataset of Integers
Integer[] ints = new Integer[n];
for(int i = 0; i < n; i++) {
ints[i] = i;
}
BinarySearch<Integer> intSearch = new BinarySearch<Integer>(ints);
// Read values to search for
while(scanner.hasNext()) {
int value = scanner.nextInt();
intSearch.search(value);
System.out.println();
}
scanner.close();
}
}
Because the implementation above is generic, you could also replace the code in the main method with something like:
Character[] alphabet = new Character[26];
final int offset = 97;
for(int i = 0; i < 26; i++) {
alphabet[i] = (char) (i + offset);
}
BinarySearch<Character> charSearch = new BinarySearch<Character>(alphabet);
charSearch.search('a');
charSearch.search('$');
charSearch.search('z');
charSearch.search('h');
Table Of Contents
