Binary search is an algorithm which is fundamental to both GCSE and A Level Computer Science for all boards. It is a very clever algorithm which reduces the time needed to search for items in large datasets dramatically.

It is important to note that in order to use binary search, your data must be sorted. Some people get mixed up with sorting algorithms and searching algorithms, grouping them together, but it is definitely worth taking a moment to organise your “algorithm toolkit” a little and make sure that searching and sorting each have their own section. Just as a reminder, see these lists:

Searching Algorithms

• Linear search
• Binary search

Sorting Algorithms

• Bubble sort
• Insertion sort
• Merge sort
• Quick sort

This article is about binary search and how to write it using Python. Before writing it in code or pseudocode, you need to understand the process thoroughly, and this is best done by doing plenty of examples by hand on paper or a whiteboard. You can see one example of a whiteboard walk-through in the video above.

Pseudocode for Binary Search

Next we need to write pseudocode for the algorithm (if this is for GCSE or A Level Computer Science). Below is a version which uses syntax from the OCR GCSE Computer Science Pseudocode guide.

// Binary search algorithm Pseudocode (OCR)

haystack = [7, 7, 22, 37, 47, 55, 57, 57, 86, 91] // MUST be sorted
needle = int(input("Enter the number you are searching for: "))
length = haystack.length
lower_bound = 0
upper_bound = length - 1
found = False

while found == False and lower_bound <= upper_bound:
    mid_point = (lower_bound + upper_bound) DIV 2
    if haystack[mid_point] == needle:
        print("You number has been found.")
        found = True
    elif haystack[mid_point] < needle:
        lower_bound = mid_point + 1
    else:
        upper_bound = mid_point - 1
        endif
endwhile
if found == False:
    print("Your number is not in the list.")
endif

The algorithm uses an important technique called divide and conquer as mentioned in the video. At each stage half of the data set is discarded, and the algorithm is re-applied to the remaining smaller data set until the search item is found or the exit condition is met.

This exit condition is key for this algorithm, and understanding why it is what it is is a good sign that you understand the whole algorithm. In essence, we have a high pointer and a low pointer, and we check the item in the middle of these two pointers to see if it is our search item. If it is, great, we exit, otherwise we move either the high or the low pointer in such as way as to “pincer-in” on our value. Again, see the video for a full explanation.

Binary Search in Python

Once you have written and understood the pseudocode, it’s time to write the algorithm in a real programming language, such as Python. You should always have a specific example in mind to test that your program behaves as expected. So, define a list (I often call this haystack) and a search item (needle), and see if you can get your program to find the needle in the haystack. And remember: the list must be sorted first!

Have a go now, and when you finish, or get stuck and need help, check out my version below.

"""Basic binary search algorithm"""

haystack = [7, 7, 22, 37, 47, 55, 57, 57, 86, 91]
needle = int(input("Enter the number you are searching for: "))
length = len(haystack)
lower_bound = 0
upper_bound = length - 1
found = False

while found == False and lower_bound <= upper_bound:
    mid_point = (lower_bound + upper_bound) // 2
    if haystack[mid_point] == needle:
        print("You number has been found.")
        found = True
    elif haystack[mid_point] < needle:
        lower_bound = mid_point + 1
    else:
        upper_bound = mid_point - 1
if found == False:
    print("Your number is not in the list.")

Comments welcome below, and don't forget to sign up to our mailing list for news and offers.

Below are products related to this article, some of which may be affiliate links.

Sharing is caring!