Notes on search algorithms from various sources:
- Introduction to Java Programming by Y. Daniel Liang (2014)
- Grokking Algorithms by Aditya Bhargava (2016)
- The Coding Interview Bootcamp: Algorithms + Data Structures by Stephen Grider
- The Ultimate Data Structures & Algorithms Series by Moshfegh Hamedani
- Programming Interviews Exposed by John Mongan et al. (2012)
- A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow (2017)
Common search algorithms
Linear search
Item-by-item search for an item in an array. Best-case scenario runtime complexity is O(1); for worst-case scenario, it is O(n).
public int linearSearch(int[] array, int target) {
for (var i = 0; i < array.length; i++)
if (array[i] == target)
return i;
return -1;
}Binary search
Only for sorted lists. First, sort; then, look at the middle item using the formula: middle = (left + right) / 2, dividing and searching recursively.
| Best | |
|---|---|
| Time complexity | O(log n) |
| Space complexity with recursion | O(log n) |
| Space complexity with iteration | O(1) |
For every time we double the number of items in the ordered array, the number of steps needed for binary search increases by just one. This pattern is unusually efficient: for every time we double the data, the binary search algorithm adds a maximum of just one more step. For linear search, every time we double the number of elements in the array, we double the number of steps we need to find something. For binary search, every time we double the number of elements in the array, we only need to add one more step.
Implementing binary search with recursion:
public int binarySearchRecursive(int[] array, int target) {
return binarySearchRecursive(array, target, 0, array.length - 1);
}
private int binarySearchRecursive(int[] array, int target, int left, int right) {
// base condition
if (right < left)
return -1;
int middle = (left + right) / 2;
if (array[middle] == target)
return middle;
if (target < array[middle])
return binarySearchRecursive(array, target, left, middle - 1);
return binarySearchRecursive(array, target, middle + 1, right);
}Implementing binary search with iteration:
public int binarySearchIterative(int[] array, int target) {
var left = 0;
var right = array.length - 1;
while (left <= right) {
var middle = (left + right) / 2;
if (array[middle] == target)
return middle;
if (target < array[middle])
right = middle - 1;
else
left = middle + 1;
}
return -1;
}Unusual search algorithms
Ternary search
Instead of dividing the list into halves at every step, we divide it into three parts with mid1 and mid2. Best-case scenario runtime complexity is O(log base 3 n).
Binary search is faster than ternary search.
Use the formula:
- partitionSize = (right - left) / 3
- mid1 = left + partitionSize
- mid2 = right - partitionSize
public int ternarySearch(int[] array, int target, int left, int right) {
int partitionSize = (right - left) / 3;
int mid1 = left + partitionSize;
int mid2 = right - partitionSize;
// base condition
if (left > right)
return -1;
if (array[mid1] == target)
return mid1;
if (array[mid2] == target)
return mid2;
// if target is in left partition, which goes
// from left to mid - 1
if (target < array[mid1])
return ternarySearch(array, target, left, mid - 1);
// if target is in right partition, which goes
// from mid + 1 to right
if (target > array[mid2])
return ternarySearch(array, target, mid2 + 1, right);
// if not in left and right partition, target is in
// middle partition
return ternarySearch(array, target, mid1 + 1, mid2 - 1);
}Jump search
Improvement to linear search. Divide list into blocks and jump to block where target may exist. Then do linear search only in that block.
The ideal number of blocks is the square root of numbers in the array.
public int jumpSearch(int[] array, int target) {
int blockSize = (int) Match.sqrt(array.length);
int start = 0;
int next = blockSize; // i.e. start of next block
while (start < array.length &&
array[next - 1] < target) {
start = next;
next += blockSize;
if (next > array.length)
next = array.length;
}
for (var i = start; i < next; i++)
if (array[i] == target)
return i;
return -1;
}Exponential search
Start with a small range, see it item is in small range. If not double the range and search again at each step.
public int exponentialSearch(int[] array, int target) {
int bound = 1;
while (bound < array.length &&
array[bound] < target)
bound *= 2;
int left = bound / 2;
int right = Math.min(bound, array.length - 1);
return binarySearchRecursive(array, target, left, right);
}