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.
Sudoku is a logic-based, combinatorial, number-placement puzzle. The objective is to fill a 9*9 grid with digits so that each column, each row and each of the nine 3*3 sub-grids contain all of the digits from 1 to 9.
Sudoku solvers employ backtracking to fill in the grid. Backtracking works by trying all the possible combinations of digits in the empty squares. If at any stage we have successfully filled all the empty cells the algorithm has found a solution and it stops. Here’s a visual aid.
My C++ code can be found here. Continue reading
Greatest Common Divisor(GCD) of two numbers, as the name suggests is the biggest number that divides both the numbers without leaving any remainder i.e. perfect division.
Take 10 and 15 for example. The biggest number that perfectly divides both of them is 5 (common sense).
This blog is centered around the fascinating world of algorithms. The blog will aim to dissect some of the most popular algorithms and provide a clear understanding of their working. If you are of the “How does it work?” kind, the blog may help ease your curiosity.