Thoughts and explanations on iterative and recursive binary search

Last time I said the next post would be about the binary search algorithm. Here it is. I will only include the iterative solution first because there's quite a bit to explain.

Iterative binary search:

Approach:

When I first approach this problem, I typically will think about how to make the problem smaller or separate them into multiple parts that are easier to do. In this case, we can just implement according to how the binary search algorithm work, which is cutting the list in half every time we check the list. Since this is not a recursive program, we want some sort of loop to keep it going. Here I used the while loop. I wrote a few comments to help me keep track of what I am doing, kind of planning out the structure of the program before I start to write it.

Explanation:

The idea in the program is setting a variable for the start index of the list and the end index of the list. Then we update those indexes according to the result of checking whether the value (the value we want to find) is on the left or right of the list. We can half the list each time by ignoring one side each time. Similar to how a base case work in a recursive function, we also want to know in a while loop when to end the loop, or else it would never return anything and keep going. When we keep updating the list and finally the list reaches a length shorter than 1, which is when the index of the right is somehow lower than the index of the left, it is when we should stop and return None, because we know we cannot find the value within the list. Else the value would be returned already.

It's not a hard problem at all if the right methods are used. Sure, there are optimizations that can be done to this code but I think the idea is there and it is good practice.

LeetCode is currently hosting a 30 day coding challenge, where there is a new question posted each day on there. It is already on question 14, but I did the first question today and I think the difficulty is pretty adequate for my level. I will be posting daily for the solutions for these questions. I might try to catch up if I have more time. More information can be found here : https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/

-Rex