# 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 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:
``````

### 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:
``````

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