Binary search - Revision history

Gus Hogg-Blake: /* Purpose */ re-use word "iterations" for clarity.

2026-01-04T11:49:46Z

Purpose: re-use word "iterations" for clarity.

← Older revision		Revision as of 11:49, 4 January 2026
Line 20:		Line 20:

	=== Purpose ===		=== Purpose ===
	The advantage of using binary search over a simpler "check every element" approach is speed. Since each step of the algorithm approximately halves the number of elements that need to be searched, each doubling of the size of the array only adds one iteration to the "while" loop above, as opposed to doubling the number of ~~steps~~. In other words, the number of steps required grows in proportion with the base-2 logarithm of the size of the array. In algorithmic complexity notation, binary search has O(log n) time complexity.		The advantage of using binary search over a simpler "check every element" approach is speed. Since each step of the algorithm approximately halves the number of elements that need to be searched, each doubling of the size of the array only adds one iteration to the "while" loop above, as opposed to doubling the number of iterations. In other words, the number of steps required grows in proportion with the base-2 logarithm of the size of the array. In algorithmic complexity notation, binary search has O(log n) time complexity.

Gus Hogg-Blake: Add section "Purpose", focusing on performance. Explain time complexity with concrete example (doubling of input requires one more step); logarithmic growth, and big-O notation.

2026-01-04T11:49:08Z

Add section "Purpose", focusing on performance. Explain time complexity with concrete example (doubling of input requires one more step); logarithmic growth, and big-O notation.

← Older revision		Revision as of 11:49, 4 January 2026
Line 18:		Line 18:
	return -1		return -1
	</syntaxhighlight>		</syntaxhighlight>

			=== Purpose ===
			The advantage of using binary search over a simpler "check every element" approach is speed. Since each step of the algorithm approximately halves the number of elements that need to be searched, each doubling of the size of the array only adds one iteration to the "while" loop above, as opposed to doubling the number of steps. In other words, the number of steps required grows in proportion with the base-2 logarithm of the size of the array. In algorithmic complexity notation, binary search has O(log n) time complexity.

Admin: Add syntax highlighting to code example

2026-01-04T11:08:42Z

Add syntax highlighting to code example

← Older revision		Revision as of 11:08, 4 January 2026
Line 3:		Line 3:
	Example in Python:		Example in Python:

	def binary_search(array, target):		<syntaxhighlight lang="python3" line="1">
	min = 0		def binary_search(array, target):
	max = len(array)		min = 0
	while min <= max:		max = len(array)
	mid = (min + max) // 2		while min <= max:
	if array[mid] < target:		mid = (min + max) // 2
	min = mid + 1		if array[mid] < target:
	elif array[mid] > target:		min = mid + 1
	max = mid - 1		elif array[mid] > target:
	else:		max = mid - 1
	return mid		else:
	# Not found		return mid
	return -1		# Not found
			return -1
			</syntaxhighlight>

Admin: Create binary search page

2026-01-04T10:57:58Z

Create binary search page

New page

Binary search is a search algorithm to find a value in a sorted array. It works by starting at the middle of the array and checking if the target value is higher or lower than the middle value. If it is lower, the algorithm then treats the bottom half as the new array and repeats the process of checking the middle value until the target value is found. If the target is higher than the midpoint, the top half of the array is used.

Example in Python:

def binary_search(array, target):
min = 0
max = len(array)
while min <= max:
mid = (min + max) // 2
if array[mid] < target:
min = mid + 1
elif array[mid] > target:
max = mid - 1
else:
return mid
# Not found
return -1