Tag Archives: binary search

Binary Search

Binary Search is a powerful algorithm to search in an ordered collection. It is a divide and conquer algorithm. Its power lies in discarding half of the search space in each iteration, thus, making it logarithmic in running time.

Lets see an example where binary search can be applied.

Finding the leftmost set bit in an integer (32 bit).

Naive approach would be to check each bit from bit position 31 to bit position 0.

Continue reading