﻿ Binary Search Game | Interactive | Computing ﻿

# Binary Search Game

This is an interactive game to help you to remember the steps in the binary search. It's called a binary search because on each step you eliminate (approximately) half of the values. A binary search only works on sorted items.

The first step is to find the item in the middle of the list - you can use the list indexes to help you. The middle item will be the mean of the first and last index of the list that you're checking - add the indexes of the first and last items and divide by two.

A list with an even number of items has no middle value - which result in the mean not being a whole number. You can round up or down (i.e. go left or right of the middle), but try to be consistent in the way you do this. I normally round down (i.e. go left of the centre) as it's easy to do that by casting the result to an integer (or by using integer division).

If the middle value you choose is the value you're looking for, the job done - you've found the item. More likely the value you're looking for will be before or after the selected item, in which case you repeat the process ignoring the items that you've just ruled out (which are faded in this case).

Most of the lists in the "questions" come from GCSE Computer Science past papers, but the value you're searching for is picked at random. I don't recall a GCSE question that asked you to find a value that wasn't in the list, but I've thrown in the odd one so that you can see what happens - if there's only one item left and it's not the one you're looking for then the item isn't in the list.