Search Algorithms

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).

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);
}