David J Nevin+= Code

Last updated: Jun 27, 2022

Binary Search

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

100
101
102
103
104
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.

100
101
102
103
104
105
106
107
108
109
110
111
112
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)

100
101
102
103
104
105
106
107
108
109
110
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)

Next: Binary Search Extended
Previous: Hashing First Steps