Binary Search Algorithm for GCSE and A Level Computer Science

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.
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.
-
Character Sets Slide Show – ASCII and Unicode for GCSE and A Level Computer Science
£10.00 Buy now -
Edexcel GCSE (9-1) Computer Science Student Book
AFFILIATE Buy now -
GCSE Computer Science OCR Complete Revision & Practice – Grade 9-1
AFFILIATE Buy now -
Key Vocabulary for OCR Computer Science GCSE – Complete Set of Word Clouds
£15.00 Buy now