Binary Search Code (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).
- 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:
|· 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)
472 total views, 1 views today