Binary Search (AQA GCSE Computer Science)

Revision Note

Test yourself

What is a searching algorithm?

  • Searching algorithms are precise step-by-step instructions that a computer can follow to efficiently locate specific data in massive datasets

  • Two common searching algorithms are:

    • Binary search

    • Linear search

  • A binary search keeps halving a dataset by comparing the target value with the middle value, going left if smaller, right if bigger, until it finds the value or realises it's not there

  • To perform a binary search the data must be in order!

  • A binary search can be performed on datasets containing numbers or words.

  • Searching for a word instead of a number is the same process, except comparisons are made based on position in the alphabet (alphabetically) instead of numerical size

Q1_BinarySearch

Example 1 - numbers

  • Perform a binary search to locate number 7 in the following dataset

Example1_BinarySearch

Example 2 - words

  • Perform a binary search to locate the word "Rock" in the following dataset

Example2_BinarySearch

Examiner Tip

If the dataset has an even number of values, the simplest way to identify the middle is to divide the total values by 2 and use that as a middle value i.e. a dataset with 8 values, 4 would be the middle value

Worked Example

Describe the steps a binary search will follow to look for a number in a sorted list [4]

Answer

  • Select / choose / pick middle number (or left/right of middle as even number) and …

  • …check if selected number is equal to / matches target number (not just compare)

  • …if searched number is larger, discard left half // if searched number is smaller, discard right half

  • Repeat until number found

  • … or remaining list is of size 1 / 0 (number not found)

Guidance

  • Can get a mark for bullet points 1 & 2 in one step (e.g. check if the middle value is the one we're looking for")

A binary search in python

# Identify the dataset to search, the target value and set the initial flag
data = [2, 4, 6, 8, 10, 12, 14]
target = 8
found = False

# Set the initial low and high pointers to the beginning and end of the data
low = 0
high = len(data) - 1

# While the low pointer is less than or equal to the high pointer
while found is False and low <= high:
  
  # Find the middle index
  mid = (low + high) // 2

  # Check if the target is at the middle index
  if data[mid] == target:
    
    # If the target is found, output a message
    found = True
    print("Target found")

  # If the target is less than the middle value, search in the left half of the data
  elif data[mid] > target:
    high = mid - 1

  # Otherwise, search in the right half of the data
  else:
    low = mid + 1

# If the target is not found, output a message
if found is False:
  print("Target not found")

Last updated:

You've read 0 of your 10 free revision notes

Unlock more, it's free!

Join the 100,000+ Students that ❤️ Save My Exams

the (exam) results speak for themselves:

Did this page help you?

James Woodhouse

Author: James Woodhouse

Expertise: Computer Science

James graduated from the University of Sunderland with a degree in ICT and Computing education. He has over 14 years of experience both teaching and leading in Computer Science, specialising in teaching GCSE and A-level. James has held various leadership roles, including Head of Computer Science and coordinator positions for Key Stage 3 and Key Stage 4. James has a keen interest in networking security and technologies aimed at preventing security breaches.

Lucy Kirkham

Author: Lucy Kirkham

Expertise: Head of STEM

Lucy has been a passionate Maths teacher for over 12 years, teaching maths across the UK and abroad helping to engage, interest and develop confidence in the subject at all levels.Working as a Head of Department and then Director of Maths, Lucy has advised schools and academy trusts in both Scotland and the East Midlands, where her role was to support and coach teachers to improve Maths teaching for all.