SPCC Computer Science

Binary Search

This is a search algorithm which is quicker for large data sets (a large array). For example if you were looking for a word in a dictionary. One disadvantage is that to make it work (like a dictionary) the array must be sorted.

Binary is more efficient than a linear search as it will find an item quicker than linear search. This is because it involves fewer comparisons. It works by repeatedly checking the middle value of an array against the a target item. Each time the item is not found the array by discarding the half that doesn't contain the item. This is a bit like looking for a word in a dictionary.

Binary Search - Dictionary example.

Imagine you were looking for the word "nepotism" in an english dictionary which has one word per page. You perform the following steps:

  1. Open the dictionary in the middle.
  2. If the item is found. Great we are done.
  3. Other wise is the word displayed earlier or later in than our search word?
  4. Say the word on the middle page is "parrot" we know that's after, so we need to check the beginning half of the dictionary. So let's set the end value to the middle - 1.
  5. Say the word on the middle page is "giraffe", we know that's before, so need to check the end half of the dictionnary. So let's set the beginning value to the middle + 1.

The Binary Search Algorithm

  1. Set beginning as the first index which is 0.
  2. Set end as the end of the array.
  3. while the beginning hasn't passed the end
  4. To find the middle set middle to (begin + end) / 2
  5. If the the value at the middle position matches the search value.
  6. We have found it and can stop.
Otherwise:
If the value at the middle position is too big

focus on the first half by moving the end position to one before the middle.

Otherwise:

Focus on the last half by moving the beginning position to one after the middle.

1

The middle is originally the length dividided by two. However set middle as (begin + end) / 2 in case begin is changed to search the latter half of the array.

2

We set mid to either mid-1 or mid+1 because we have already checked the value at mid, so we don't need to check it again.

Here is the code using the pseudocode above as comments.

int[] nums = {13, 26, 37, 49, 52, 65, 78, 87, 98, 109};
int Search = 49;

// Set beginning at the first index which is 0.
// Set end as the array length

int begin = 0;
int end = nums.Length;

// while the beginning hasn't passed the end

while (begin <= end)
{
    // find the mid point

    int mid = (end + begin) / 2;

    // If the value at the middle position matches the search value

    if (nums[mid] == Search)
    {
        // We have found it and can stop.
        Console.WriteLine("Found at array position: " + mid.ToString()); // displaying position found at.
        return;
    }
    else if (nums[mid] > Search) // if the value at the middle is too big
    {
        end = mid - 1; // focus on the first half by moving the end position to the middle.
    }
    else // name is in the second half...
    {
        begin = mid + 1; // check the end half only
    }
}

// We got to the end of the array without finding...
Console.WriteLine("Not found");

Find out more

Check BBC Bitesize by clicking here.