DSA Walkthrough - 02

Intro

• The problem is, in a given array, there will be a index where the array was rotated. We have to use binary search to find the given target.
• The entire array after rotation is not sorted, and we should not sort the array again, we have to use binary search in the entire unsorted array

First approach

• The only question i got in my mind after seeing this is, if the array is not sorted completely then how binary search works ?
• After seeing the given test cases i was able to get the idea that, one part of the array is always sorted from the mid.
• So we follow the same procedure as binary search but with a little bit of checks and addition.

Solution

• So the solution is that, We find the mid of the array as we do for binary search. But after finding the middle element, we check the left and mid element to see if left <= mid, this proves that, the left part of the array is sorted. if not the right part of the array is sorted.
• Now that we found which part of the array is sorted, we have to check if the target element is in the sorted part, for that we check this condition if(target > left && target < mid).
• The above condition is very obvious that the target element should lie between left and middle element. if the condition is true, we go to next step of the binary search which is removing the unnecessary part of the array.
• So the final step would look like the given code snippet below

Code

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();

        int left = 0;
        int right = n-1;
		
		while(left <= right){
            int mid = left + (right-left)/2;
            
            if(nums[mid]==target) return mid;
            if(nums[left]<=nums[mid]){
                if(nums[left]<=target && target < nums[mid])
                 right = mid -1;

                else left = mid + 1;
            }

            else{
                if(nums[right]>=target && target>nums[mid])
                left = mid + 1;
                else right = mid -1;
            }
     }

    return -1;

    }

};

Conclusion

This was a fun problem with a twisted topping of binary search. Hint : There will be always a sorted part in the array Check out my other DSA walkthrough : https://maddyscave.vercel.app/blog/DSA-01