Skip to main content

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 popular rotated array problem in leetcode. Which are given below:

153. Find Minimum in Rotated Sorted Array:

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
  • [4,5,6,7,0,1,2] if it was rotated 4 times.
  • [0,1,2,4,5,6,7] if it was rotated 7 times.
We have to find out, the minimum number in the rotated array. If we use brute force technique and search through the whole array, we can easily find out the solution. But it will take O(n) time. Which is very time consuming. So, we have to find out more efficient way to solve this. If we look at question we have something like a sorted array, so we can apply binary search. But for this we have change some of the condition.

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

If we look very closely to the array, we can see the minimum number in the array is smaller than it previous and next element. So, we find out the mid element in binary search. If it satisfied the condition we can return the number.

If it doesn't, we have to choose a right or left side. Where we can continue our searching. So, we simply choose the side where it isn't sorted and continue the searching.

Time complexity: O(logn)

Problem Link: Find Minimum in Rotated Sorted Array - LeetCode

33. Search in Rotated Sorted Array:

In this problem, we have to find a element in the rotated array and return it's index. If we don't find the element in array we simply return -1.

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

In this solution, we divide the array into two part and search through the left or right. First, we find out the mid, if the element is in the middle point return the index. Else we have to look at the left or right side. If the element in the right side, we continue searching in right side. Otherwise in the left side.

Time complexity: O(logn)

Problem Link: Search in Rotated Sorted Array - LeetCode

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

Upper bound and Lower bound!

Lower bound: In binary search, the lower bound is the lowest position where the value could be inserted without breaking the ordering. In the C++ standard library, this bound will be represented by an iterator referencing the element before which the value could be inserted.  STL: int lower = lower_bound(vec.begin(), vec.end(), target); That function will return a int value, where we can put the target value with the compromising the sorted system. Upper bound: In binary search, the upper bound is the highest position where the value could be inserted without breaking the ordering. In the C++ standard library, this bound will be represented by an iterator referencing the element after which the value could be inserted.  STL: int upper = upper_bound(vec.begin(), vec.end(), target); That function will return a int value, where we can put the target value with the compromising the sorted system.
Post a Comment
Read more

Two Pointer Technique

The two-pointer technique is a simple and effective technique that is used in competitive programming. It helps programmer to efficiently solve array problem. In two-pointer we take two pointer at the start and the end. That pointers started to iterate the whole array and solve problem according to a programmer. Suppose, we have an array n which consists m number of values. Now, if we want to sum all the element of the array then we have to iterate the whole array and sum all the element. Which will take O(n) time. n = [4, 5, 2, 4, 9, 4] But, in two-pointer technique we can solve this problem in O(n/2) time. Which is more efficient than traditional way. In the code, we used two variable st which point at first element of the array and en which point at the last element of the array. After this, we take a while loop which condition is st should be less than en. If the condition does not meet the value, then loop will break. In the loop, we summed the first value and last value that are ...
Post a Comment
Read more