Finding Something Fast

Part of Binary Search · Section 1 of 8

IntroductionUnit: 3.1 Fundamentals of AlgorithmsGCSE

Binary search is like guessing a number between 1 and 100 when the friend only says "higher" or "lower". You do not start at 1. You guess 50, and every answer lets you throw away half of the numbers. Binary search does the same on a sorted list: check the middle item, decide which half the target must be in, discard the other half, and repeat.

Binary search for 31 in the sorted list 3, 7, 11, 18, 24, 31, 36, 42, 55, 69, at indexes 0 to 9. Step 1: the search range is all ten items, the middle is index 4 with value 24, and 31 is higher. Step 2: the search range is indexes 5 to 9, the middle is index 7 with value 42, and 31 is lower. Step 3: the search range is indexes 5 and 6, the middle is index 5 with value 31, so it is found. Items in the search range are blue, ruled out items are grey and the found item is green.

Binary search needs a sorted list. Each check looks at the middle of the search range, then rules out the half that cannot hold the target. Here 31 is found in 3 checks. The most checks grow very slowly: 10 items need at most 4 checks, and 1,000,000 items need at most 20.

This introduction covers Finding Something Fast within Binary Search for GCSE Computer Science. Revise Binary Search in 3.1 Fundamentals of Algorithms for GCSE Computer Science with 15 exam-style questions and 10 flashcards. This is a high-frequency topic, so it is worth revising until the explanation feels precise and repeatable. It is section 1 of 8 in this topic. Use this introduction to connect the idea to the wider topic before moving on to questions and flashcards.

Practice questions for Binary Search

Which of the following is a requirement before binary search can be used?

  • A. The list must contain an even number of items
  • B. The list must be sorted in order
  • C. The list must be stored in a 2D array
  • D. The target value must be in the first half of the list
1 markfoundation

Describe how a binary search algorithm finds a target value in a sorted list.

3 marksstandard

Quick recall flashcards

What technique does binary search use?
Divide and conquer - repeatedly halves the search space
What is the time complexity of binary search?
O(log n) - logarithmic time

Next

Binary Search or Linear Search?

15 questions on Binary Search: practise free

Instant marking, adaptive difficulty and spaced-repetition flashcards — all aligned to your exam board.

Start revising free →

PrepWise is a trading name of A3M Quality Solutions Limited, registered in England and Wales, company number 14959172. Registered office: 202 Stroud Road, Gloucester, GL1 5LA. ICO registration ZC267069.