Binary Search

Test yourself on Binary Search with exam style questions, marked instantly.

Flashcards that come back just before you would forget them.

A revision plan that remembers what you know and shows what to do next.

See which topics you have nailed and which need another look.

Quiz yourself on Binary SearchGet your flashcardsBuild my revision planTrack my progress

Finding Something Fast

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.

Binary Search or Linear Search?

Feature Binary Search Linear Search
Method Check the middle item, discard half, repeat Check each item one by one from the start
List must be sorted? Yes No
Speed on a large list Much faster, because half the items go each step Slower, because it may check every item
Best used when The list is large, sorted and searched often The list is short or unsorted

Deep Dive: The Steps of Binary Search

  1. Make sure the list is sorted.
  2. Set the low pointer to the first position and the high pointer to the last position.
  3. Find the midpoint: (low + high) DIV 2. DIV means divide and drop any remainder.
  4. Compare the middle item with the target.
    • Equal: the target is found. Stop.
    • Target is larger: it must be in the right half, so set low to mid + 1.
    • Target is smaller: it must be in the left half, so set high to mid - 1.
  5. Repeat from step 3. If low becomes greater than high, the target is not in the list.

Deep Dive: Worked Example

Find 23 in [2, 5, 8, 12, 16, 23, 38] (positions 0 to 6):

StepLowHighMidpointMiddle itemDecision
10631223 is bigger, keep the right half
246523Equal: found at position 5

Only two items were checked. A linear search would have checked six.

Searching for 10 in the same list: low 0, high 6, mid 3 (12) so high becomes 2. Mid 1 (5) so low becomes 2. Mid 2 (8) so low becomes 3. Now low (3) is greater than high (2), so 10 is not found.

Deep Dive: Pseudocode

found = False
low = 0
high = numbers.length - 1
while low <= high AND found == False
    mid = (low + high) DIV 2
    if numbers[mid] == target then
        found = True
    elseif numbers[mid] < target then
        low = mid + 1
    else
        high = mid - 1
    endif
endwhile

This follows OCR reference language. AQA and Edexcel questions use a similar structure with their own pseudocode style.

Memory Trick

Sorted first, then halve. Think of looking up a name in a printed phone book: you open it near the middle, see whether your name comes before or after, and ignore the other half.
Low and High mark the edges of what is still being searched. When Low passes High, nothing is left.

Exam Tips

  • Always say the list must be sorted. This is the most common mark point for binary search.
  • Show each step: write down low, high, the midpoint and the middle item every time.
  • Compare with linear search: binary search is faster on large sorted lists, but linear search works on unsorted lists and needs no sorting first.
  • Common mistake: searching the wrong half. If the target is larger than the middle item, keep the right half.

Make this stick

Signing in gives access to all PrepWise features.

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.