Hello and welcome back, brave human being,

At this point, I’m flakier than your ex 😭 but I took some time off to rest, and now I’m back.

Our ability to stay focused declines when we focus on one task for a long period of time.

The brain can run down quicker than you might expect.

That is why it’s very important to take a break.

This is true for everything in life, especially the LeetCode problems we are solving.

When you’ve been stuck for a while, take a break. Breathe. Take a walk, and try again.

Now, let’s pick up where we left off.

Day 17:  35. Search Insert Position

Day 17:  35. Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not found, return the index where it would be if it were inserted in order.

Let's set an example…

Input: nums = [1,3,5,6], 

target = 5

Output: 2

This is a perfect example of how to use binary search in a problem.

We start by initializing two variables:

L = 0 
R = Array.size()-1

At each iteration, we are going to calculate the middle by doing:

middle = (left + right)/2; 

Once we’ve computed middle, we will evaluate if middle is our solution.

if(nums[middle] == target|| target<nums[middle] && target>nums[middle-1])

The later part of the condition evaluates whether the number does not exist in the array; if so, would the middle position be the corresponding index?

If it’s our solution, we break the recursion.

Otherwise, we have to evaluate where we should go next.

target < array[middle]. Then: left = middle - 1

target > array[middle]. Then: right = middle + 1

Let’s dig in with an example:

Final Solution:

Search Insert Position

        #include <vector>

        using namespace std;

        class Solution {
        public:
            int middle;  

            void binarySearch(vector<int>& nums, int target, int left, int right){
                middle = (left + right) / 2; 

                if (nums[middle] == target || (target < nums[middle] && target > nums[middle - 1]))
                    return; 
                else if (nums[middle] > target) {
                    right = middle - 1; 
                    binarySearch(nums, target, left, right); 
                }
                else {
                    left = middle + 1; 
                    binarySearch(nums, target, left, right); 
                }
            }

            int searchInsert(vector<int>& nums, int target) {
                int left = 0; 
                int right = nums.size() - 1;
                if (target < nums[0])
                    return 0; 
                if (target > nums[nums.size() - 1])
                    return nums.size(); 
                binarySearch(nums, target, left, right); 
                return middle; 
            }
        };
    

See you Thursday for a new problem and solution and JOBS!

Denisse