Write pseudocode for the binary search algorithm and state, with an explanation, it's worst case complexity in big-O notation

procedure binarySearch(A[], start, end, item): if start <= end: i = ceil((start + end) / 2)
if A[i] = item: return i if A[i] > item: return binarySearch(A[], i + 1, end, item) if A[i] < item: return binarySearch(A[], start, end -1, item) else: return -1 //item not found in A[]
Big-O worst case complexity is O(log(n)):Worst case occurs when the search reduces the array down to one element as this takes the most number of steps. In this case the number of steps taken is how many times the array, of length n, is halved until one element is left i.e. n/2^steps = 1. After rearranging this equation, the value of the steps variable is calculated by finding log2(n). In big-O notation the base of the log is irrelevant so it becomes O(log(n)).

YB
Answered by Yagna B. Computing tutor

1403 Views

See similar Computing A Level tutors

Related Computing A Level answers

All answers ▸

What is the difference between compile-time errors and runtime errors?


One member of a chess club sends a text file saved in Unicode. What meant by the term "Unicode" and why might this be necessary?


Describe the difference between passing parameters into a function by reference and by value? Indicating how this may lead to unexpected outputs.


A computer stores floating point numbers of size 1 byte, with 3 bits for the mantissa and 5 bits for the exponent. State what the effects would be on the stored numbers if instead 5 bits were used for the mantissa and 3 bits were used for the exponent.


We're here to help

contact us iconContact ustelephone icon+44 (0) 203 773 6020
Facebook logoInstagram logoLinkedIn logo

MyTutor is part of the IXL family of brands:

© 2025 by IXL Learning