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

Easiest way to find out which power of number is big?

If you are given two number with its power and told you which number is big. How do you calculate it. For, instance you would say binary exponentiation technique. But this is bit harder when the test case number is bigger. There is also an easy way to solve this problem. Suppose you are given 2^18 and 6^12. Then, you just take logarithm in both numbers. Then it will become 18*log2 and 12*log6. Logarithm function will break this number and make it a little number. which can be compare easily. But for this you have to Double number type, or you will get an error message. Problem:  Problem - 987B - Codeforces Code: void solve() {    ll a,b;    cin>>a>>b;    double num1 = b*log(a);    double num2 = a*log(b);    if(num1==num2) cout<<'='<<endl;    else if(num1>num2) cout<<'>'<<endl;    else cout<<'<'<<endl; }
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; } Time Complexity: O(sqrt(n))       
Post a Comment
Read more