The divide and conquer search method.

The sequential searching through all data entries one by until until we find a match.

Time complexity is O(n).

def linear_search(data, target):
	for i in range(len(data)):
		if data[i] == target:
			return True
	return False

The worst-case runtime of a linear search would be O(n).

Binary Search (Iterative)#

Note: assumes that the array on which the search will take place is sorted in ascending order. We start in the middle of the data. If the result is our search term when we finish searching. If not, and is smaller than the target we repeat the process on the upper half of the data, otherwise if the middle is larger than the target search the lower half.

In each case we pick a new mid point and choose to search either the upper half or lower half of the data. This is of course much more efficient than an iterative.

def binary_search_iterative(data, target):
	low = 0
	high = len(data) - 1

	while low <= high:
		mid = (low + high) // 2
		if target == data[mid]:
			return True
		elif target < data[mid]:
			high = mid - 1
		else:
			low = mid + 1
	return False

The worst-case time complexity of a binary search is O(logn).

Binary Search (Recursive)#

def binary_search_recursive(data, target, low, high):
	if low > high:
		return False
	else:
		mid = (low + high) // 2
		if target == data[mid]:
			return True
		elif target < data[mid]:
			return binary_search_recursive(data, target, low, mid-1)
		else:
			return binary_search_recursive(data, target, mid+1, high)