Binary Search : LeetCode Series-2

This blog post will focus on concepts of Binary search and a LeetCode Easy and Medium level question on the topic of Binary Search. Even though the overview of Binary Search is given, this blog is written in context to the people who are already familiar with the key or basic concepts of the topic and have knowledge of the implementation.

We will get started with a basic question on LeetCode as mentioned below. You are requested to first try out the question yourself and then look at the solution after some time.

Ques - 35. Search Insert Position

Difficulty: Easy , Acceptance: 44.4%

Approach

The question can be broken in two parts -

1. Finding the target element
2. Adding the target element (if not found)

Part I - Finding Target Element - This is the basic implementation of Binary search where we set three variables known as start, end and middle to the beginning, ending and middle of the array. Then we compare the middle element with the target element and set positions of start or end respectively to break our array into two halves (out of which only one is useful to us). This leads to breaking down of arrays into halves over and over till we find the desired element (or target). This can be better seen by the illustration below.

Part II - Usually, when the target is not found, we return -1 to show that the target element is missing. However, in this case, the optimum position to insert target element is asked. If we notice carefully, if the element is not found, the mid element stops at a position prior to the optimum position. Hence, the optimum position for that case would be mid+1.

CODE:

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int start=0;
        int end=nums.size()-1;
        int mid= (start+end)/2;
        
        if(target<nums[0]) return 0; // base case
        
       while(start<=end)
       { // beginning of binary search implementation (PART 1)
           mid=(start+end)/2;
            if(target==nums[mid])
             {
               return mid;
             }
           if(target<nums[mid])
             {
               end=mid-1; 
               mid=(start+end)/2;
             }
           else if(target>nums[mid])
             {
               start=mid+1;
               mid=(start+end)/2;
             }
       } 
       //PART 2 if element was not found
       return mid+1; // returning optimum position
     }
};

Ques - 34. Find first and last of element in a sorted array

Difficulty: Medium , Acceptance: 42.6%

Approach

This question can be solved in two ways:

1. Linear Search
2. Binary Search

For this particular solution we solve the problem with Binary search. The first step will be to find the target number (be it in any index) and store its location in a variable called temp. For this we will apply basic binary search. If mid == target condition is satisfied, we will apply two seperate loops from position of mid to increment and decrement it in both direction and find the upper and lower bound indexes respectively. We will then store both these value in the vector ans and the final positions are returned.

If the target is not found, we will simply come out of the loop and [-1,-1] is returned.

CODE:

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans;
        int start= 0;
        int end=nums.size()-1;
        int i=-1;int j=-1;
        while(start<=end)
        {
            int mid= (start+end)/2;
            if(nums[mid]==target)
            {       int temp=mid;
                    while(mid>0 and nums[mid-1]==target){
                        mid--;
                    }
                    i=mid;
                    while(temp<nums.size()-1 and nums[temp+1]==target)
                    {
                        temp++;
                    }
                    j=temp;
                    ans.push_back(i);
                    ans.push_back(j);
                return ans;
            }
            else if(nums[mid]>target)
                end=mid-1;
            else 
                start=mid+1;
    }
        ans.push_back(-1);
        ans.push_back(-1);
        return ans;
    }
};

That is all for this particular blog, but stay tuned for many more LeetCode series! I hope you are clear with the explanation and this helped.

Keep coding Dummies!