Binary Search

Download:

Binary Search

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

Simplified Explanation:

  1. Start at the middle item in the list.
  2. If the middle item is the one to be found, the search us complete.
  3. If the item to found is lower than the middle item, discard all the items to the right.
  4. If the item to be found is higher than the middle item, discard all items to the left.
  5. 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)

 303 total views,  1 views today