Download:
Binary Search (Code Needs To Be Copied Into Python)
Townlist (Text Document Needed For Python File to Work)
Note: Make sure that townlist and the python file is in the same folder for the program to work. Remove/add comments where needed in order test out variants
Binary Search: (GCSE & A-Level)
The Binary Search is an efficient algorithm for finding an item in a sorted list. To perform a Binary Search, start at the middle item in the list and repeatedly divide the list in half. (Divide and Conquer approach).
Simplified Explanation:
- Start at the middle item in the list.
- If the middle item is the one to be found, the search us complete.
- If the item to found is lower than the middle item, discard all the items to the right.
- If the item to be found is higher than the middle item, discard all items to the left.
- Repeat from step 2 until you have found the item or there are no more items in the list.
Binary Search in Python:
| Advantages: | Disadvantages: |
| · Faster compared to a linear search | · Has to be a sorted list |
| · Consistent number of loops/operations to find the search term |
Big O Notation of Binary Search (A-Level):
| Best Case: | Average Case: | Worst Case: |
| · Constant | · Logarithmic | · Logarithmic |
| · O(1) | · O(log n) | · O(log n) |
Recursive Binary Search: (A-Level)
