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)).

Answered by Yagna B. Computing tutor

1289 Views

See similar Computing A Level tutors

Related Computing A Level answers

All answers ▸

Explain why it is important to check the email address with JavaScript and again when it reaches the server.


What are the different development methodologies and what are their advantages and disadvantages?


Describe the process of a binary search.


Convert 10101100 to decimal.


We're here to help

contact us iconContact usWhatsapp logoMessage us on Whatsapptelephone icon+44 (0) 203 773 6020
Facebook logoInstagram logoLinkedIn logo

© MyTutorWeb Ltd 2013–2025

Terms & Conditions|Privacy Policy
Cookie Preferences