Skip to main content

Binary Search Problems!


1. Find the first and last position of a element in sorted array:
 
In this problem, they will gave us a sorted array and a number. We have to find out the first and last position of that element.
if the target is not found, we have to return [-1,-1]. We have to solve this problem in O(log_n) time. So, we have to use binary search algorithm.

Input:     nums =  [5 ,7 ,7, 8, 9, 10], target=7
Output:  [1, 2]

Solution:
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int st=0,en=nums.size()-1;
        int index1=-1,index2=-1;
        while(st<=en){
            int mid = st + (en-st)/2;
            if(nums[mid]>target) en = mid-1;
            else if(nums[mid]<target) st = mid+1;
            else if(nums[mid]==target){
                index1 = mid;
                en = mid-1;
            }
        }
        int st1=0,en1=nums.size()-1;
        while(st1<=en1){
            int mid = st1 + (en1-st1)/2;
            if(nums[mid]>target) en1 = mid-1;
            else if(nums[mid]<target) st1 = mid+1;
            else if(nums[mid]==target){
                index2 = mid;
                st1 = mid+1;
            }
        }
        return {index1,index2};
    }
};

Time complexity: O(log_n)

2. Search Insert Position:

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

Input:    nums = [1,3,5,6], target = 5
Output: 2

Solution:
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int st=0,en=nums.size()-1;
        int in = -1;
        while(st<=en){
            int mid = st + (en-st) /2;
            if(nums[mid]==target){
                return mid;
                break;
            }
            else if(nums[mid]>target) en = mid-1;
            else if(nums[mid]<target) st = mid+1;
        }
        return st;
    }
};

Time complexity: O(log_n)
Labels:

Comments

Post a Comment

Popular posts from this blog

Rotated Array(Modified Binary Search)

  A modified binary search is an algorithm that can be used to find an element in a sorted array by using a different base or condition than the standard binary search. It is an extension of the bitwise binary search and has a similar running time of O(log N) . There are different ways to modify the binary search algorithm, such as using a different number base, finding the minimum element in a rotated and sorted array, or comparing the input element with the first, last and middle elements of the array. Today we will look at rotated array problems. A rotated array is an array that is sorted in ascending order but shifted to the right by some unknown number of positions. For example, [0,1,2,4,5,6,7] is a sorted array and [4,5,6,7,0,1,2] is a rotated array with 4 positions shifted. A rotated array can also be seen as two sorted subarrays concatenated together. For example, [4,5,6,7] and [0,1,2] are two sorted subarrays that form the rotated array [4,5,6,7,0,1,2]. There are two very ...
Post a Comment
Read more

Two Pointer Problems

Here we have given some important two pointer problems below: 1. Valid Palindrome: A phrase is a  palindrome  if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. Given a string  s , return  true  if it is a  palindrome , or  false  otherwise .  -> Solution: class Solution { public:     bool isPalindrome(string s) {       int low=0;       int high=s.length()-1;       while(low<high){           while(!iswalnum(s[low]) && low<high){               low++;           }           while(!iswalnum(s[high]) && low<high){               high--;           } ...
Post a Comment
Read more

Find out all divisor in efficient way!

1. Brute force approach:   In this process, we use a for loop and iterate the whole 1 to n number. Then, we find out all the divisors by one by one. It is not a optimal solution for this problem. Because, it will take O(n) time to find out all divisors. int main() {     optimize();     ll n;     cin>>n;     for(ll i=1; i<=n; i++)     {         if(n%2==0) cout<<i<<" ";     }     cout<<endl;     return 0; } Time complexity: O(n) 2. SQRT approach:   In this process, we only iterate in the loop by half of the numbers. Because, if we see we don't need to go through whole n numbers. int main() {     optimize();     ll n;     cin>>n;     for(ll i=1; i * i<=n; i++)     {         if(n%2==0) cout<<i<<" "<<n/i<<endl;     }     return 0; } Tim...
Post a Comment
Read more