Simple binary search

 

Simple binary search

Given a sorted collection of items S and a value k to locate:

·         Repeat until k is found or no more items exist

o   Check the middle item

o   If it is larger than k, remove all items to the right (including the middle item)

o   If it is smaller than k remove all items to the left (including the middle item)

How can we express this in O-notation? It’s definitely faster than O(n) and it isn’t a constant O(1).

·         How many times can you divide a n in half before it becomes less than 1?

·         How many times can you multiply 1 by 2 before it becomes greater than n?

The algorithm described is a variation of binary search, which is a divide and conquer algorithm that has a time complexity of O(log n), where n is the number of items in the collection S.

In each step of the algorithm, the size of the remaining collection is halved, which means that the running time of the algorithm increases very slowly as the size of the input grows. This is why binary search has a time complexity of O(log n), which is faster than O(n).

To answer your questions:

·         You can divide n in half a maximum of log_2(n) times before it becomes less than 1. This is because log_2(n) is the exponent to which we need to raise 2 in order to get n.

·         You can multiply 1 by 2 a maximum of log_2(n) times before it becomes greater than n. This is because 2^log_2(n) equals n.