Solving the Rotated Sorted Array Search Problem: A Helpful Solution.

The Problem:

An array is give, but it is randomly rotated. Right to Left rotation. We have to find a specified element in the array and return its index. The main issue would be the required time complexity being O(logn).

The Solution:

Of course, we can use our dear friend Nested Loops. But the time complexity is specified explicitly.

We are going to use something called a binary search.

But here is my understanding. logn mostly means halving of search space after each iteration. while loop works best for this, so I started with while loop without really understanding that I was implementing Binary Search.

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int head=0;
        int tail=nums.size()-1;
        while(head<=tail){ // kinda like while True
            int mid=(head+tail)/2; // finding the mid for each iteration.

            if (nums[mid]==target) return mid; // after some iterations, mid will reach target.

            // we are going to do double constraints, which first check where mid is. is it in the
// roated part of the array or the original? then we move to basic constraints based on it.
            if (nums[head]<=nums[mid]){
                if (nums[head]<=target && target< nums[mid]){
                    tail=mid-1;
                }else{
                    head=mid+1;
                }
            }
            else{
                if(nums[mid]<target && target<=nums[tail]){
                    head=mid+1;
                }
                else{
                    tail=mid-1;
                }
            }
        }
        return -1;

    }
};

Time complexity is O(logn).

---

Remember, halving of search space is mostly done with while loop. Though it is not to be mis understood that for loop can be used to implement O(logn).

Good Night.