Basic Search Algorithms: Linear vs Binary

Explanation


Linear Search: checking each element of an array in turn for a required value
Binary Search: checking the middle of a sorted array and discarding the half that does not contain the required value

Type Requirement Performance
Linear Search no requirement O(n); Time proportional to array length
Binary Search must be sorted O(log n); Time proportional to log of array length

bigo-3

As you can see from the graph above, the average search time of an O(n) algorithm (linear search) increases linearly while the average search time of an O(log n) algorithm (binary search) increases logarithmically, meaning the increase in search time tends towards 0.


Code Example (in Python)


Linear Search

List = [4, 3, 10, 7, 2, 1]
Found = False
Index = 0
SearchValue = input(int("Enter a value to search: "))

while Found == False and Index < len(List):
	if List[Index] == SearchValue:
		Found = True
	Index += 1

if Found == True:
	print("Value found at position:", Index)
else:
	print("Value not found")

Binary Search

List = [1, 2, 5, 6, 9, 10, 11] #Must be ordered
Found = False
SearchFailed = False
Lower = 0 #Position of minimum value
Upper = len(List) - 1 #Position of maximum value
SearchValue = input(int("Enter the value to be searched: "))

while !Found and !SearchFailed:
	Middle = (Lower + Upper) // 2 #Use // to return a whole number
	if List[Middle] = SearchValue:
		Found = True
	else:
		if Lower >= Upper:
			SearchFailed = True
		else:
			if List[Middle] < SearchValue:
				Lower = Middle + 1
			else:
				Upper = Middle - 1

if Found:
	print("Value found at:", Middle)
else:
	print("Value not found")

A Level Computer Science Syllabus


AS Requirement:

  • Write algorithms/program code to process array data including
    • searching using a linear search

A2 Requirement:

  • write a binary search algorithm to solve a particular problem
    • show understanding of the conditions necessary for the use of a binary search
    • show understanding of how the performance of a binary search varies according to the number of data items

(Updated for the 2017-2019 CIE Syllabus)

Show Comments