A searching algorithm is a sequence of instructions used to find a particular item of data in a list or confirm that the item is not present.
The two standard searching algorithms are binary search and linear search.

Binary search repeatedly halves the part of a list that still needs to be searched.
Binary search can only be used when the list is already sorted.
Binary search works by:
- Finding the middle value of the remaining search area.
- Comparing the target with the middle value.
- Stopping if the target equals the middle value.
- Discarding the middle value and everything above it if the target is smaller.
- Discarding the middle value and everything below it if the target is larger.
- Repeating the process with the remaining half.
- Concluding that the target is not present if no values remain.
If there are two possible middle values, either can be chosen as long as the same approach is used consistently.
Binary search is efficient because each unsuccessful comparison removes approximately half of the remaining search area.
Binary search can be recognised in code or pseudocode by a middle position being calculated and the search boundaries being changed to discard approximately half of the remaining search area.

Linear search starts at the beginning of a list and checks each item in order until the target is found or the end of the list is reached.
Linear search works by:
- Starting with the first item.
- Comparing it with the target.
- Stopping if the values match.
- Moving to the next item if they do not match.
- Repeating until the target is found or every item has been checked.
- Concluding that the target is not present if the end of the list is reached without a match.
Linear search does not require the list to be sorted.
Linear search can be inefficient for large lists because it may need to check every value.
Linear search can be recognised in code or pseudocode by values being checked one at a time from the beginning until the target is found or the list ends.

A sorting algorithm is a sequence of instructions used to arrange data into a particular order, such as numerical or alphabetical order.
The three standard sorting algorithms are bubble sort, insertion sort, and merge sort.

Bubble sort repeatedly compares adjacent values and swaps them when they are in the wrong order.
A complete journey through the list is called a pass.
During an ascending bubble sort, adjacent values are compared from left to right and swapped when the value on the left is larger than the value on the right.
Repeated swaps cause larger values to move towards the end of the list.
Bubble sort continues until a complete pass occurs with no swaps.
Bubble sort can be recognised in code or pseudocode by adjacent values being repeatedly compared and swapped and passes continuing until one occurs with no swaps.

Merge sort uses a divide-and-merge approach.
The divide stage repeatedly divides the list into smaller sub-lists until every sub-list contains one value.
A single value is already considered sorted.
The merge stage combines neighbouring sub-lists back together in sorted order until one complete sorted list remains.
When merging two sorted sub-lists, the smallest remaining values are compared and the smaller value is placed into the new sorted list.
Merge sort can work with an odd number of values; either half can contain the extra value as long as the approach is used consistently.
Merge sort can be recognised by its distinctive pattern of repeatedly dividing a list into single-item sub-lists and then progressively merging them back together in sorted order.

Insertion sort treats the list as two sections: a sorted section and an unsorted section.
Initially, the sorted section contains only the first item.
Each item from the unsorted section is taken in turn and inserted into the correct position in the sorted section.
Values larger than the item being inserted are shifted to the right until the correct insertion position is reached.
Insertion sort is complete when every item has been inserted into the sorted section.
Insertion sort can be recognised in code or pseudocode by starting from the second item, working backwards through the sorted section, shifting larger values to the right, and inserting the current value into the remaining gap.

Module Review