In lecture, we talked about the idea of the binary search algorithm, but did not end up implementing it. This reading will look at the implementation for the algorithm since it's not uncommon to be asked to implement the code for this algorithm on an interview for a job involving programming. The end of the reading is a reference of the complexities of the operations we have learned so far
In lecture, we discussed how to search a sorted array for a value. The naive algorithm that just starts at the beginning and traverses to the end or until it finds the element. With the language we discussed in lecture, we would say that worst case this "linear search" would take O(n)
time where n
is the number of elements in the array.
We then discussed a smarter idea which divides the array in half repeatedly. Start by looking at the middle element of the array and compare it to the target value, there are three options