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