Searching Algorithms

Question 1

Basic Algorithm for Binary Search

Answer 1

If value == middle -> value found
If value < middle -> end = mid - 1
if value > middle -> start = mid + 1

Question 2

Setup condition for a binary search (inc while loop)

Answer 2

low = 0
high = len(array)-1

low <= high

If low goes above high, then the value is not found

Typically you will return low or ValueError

Question 3

Best & Worst Case of Binary Search

Answer 3

Best Case: loop stops immediately, item is in the middle of the loop, so it’s just O(m), where m is cost of comp

Worst Case: item is at start/end, therefore complexity is O(log n * m)
This is because each iteration of the loop halves the working space, which is log n