Simple and Elegant algorithm to search an element in a sorted array which only takes log n time..
Let’s understand this algorithm in Harry Potter terms. It is the 3rd year of Harry Potter’s wizardry journey and Hogwarts is being threatened by Animagi Sirius and WareWolf Lupin.
Snape enters the classroom says his famous line “Turn to page 394”.
While Ron (Ronald Weasley) start turning his page one by one. Hermione comes up with a different approach. She opens her book(with 1000 pages) from the middle checks the page number. Its was around 500. As 394 was smaller than 500. Now she find the middle page between 0 and 500 and opens page number 250. Then again by finding a middle between 250 and 500 as 394 is greater than 250, she reaches page number 375.
See in simple 3 iterations was closer to page number 394. Whereas Ron was still on 3rd page.
Following the Hermione’s approach I have written these 2 functions to search elements in sorted array.
Iterative Version:
Recursive Version:
Note: By checking the Index page she could have reached the page 394 even faster. So let’s study Hashing Soon.
Binary Search Algorithm is a tool which easily modified solve complex problems. We will see such Problems in my upcoming posts.
Challenge yourself with this trivia app :
