search in reversed sorted array, O(log n)!

Example --

 

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

 

Now if we try to place this nums on the graph  we get:

We get two lines l1  and l2.

So if we could find the pivot (smallest value) in the graph we can easily divide the NUMS array into   2 parts then apply  BINARY SEARCH  to find the target value and return the position if present  else -1;

1. GETPIVOT

 

    int getPivot(vector<int>& nums , int size){

        int s = 0, e= nums.size()-1, mid=s + (e -s)/2;

      while(s < e){

          if(nums[mid] >= nums[0]){

              s =mid+1;

          }

          else

            {e = mid;}

          mid=s + (e -s)/2;

      }

      return s;

    }

 

 

 

We initalise the start , end and mid in the array.

 

Start = 0 ,

End = 7 - 1 = 6

Mid = start + ( end - start ) / 2  = 3

 

 

                            We check if the  nums[mid] >= nums[0]

                                If true we are still on the first line  L1. and we need to go further more in right side.

Therefore we change the  position of Start to mid + 1;

 

            if nums[mid] <= nums[0] that means we are on the second line L2.

Start = Mid + 1 = 3

End = 6

Mid = start + ( end - start ) / 2 = 4.

 

Which does not satisfy the condition of nums[mid] >= nums[0],

We move end towards center.

 

End = mid;

 

            Loop condition of start < end , does not satisfy. We get out of the loop.

RETURN THE POSITION OF START

    

2. Binary Search --

 

   int bSearch(vector<int>& nums, int s, int e , int target ){

      int mid = s+(e-s)/2;

      while(s<=e){

        if(nums[mid]== target)

          return mid;

        else if(nums[mid] < target)

          s = mid +1;

        else

          e = mid -1;

        mid = s+(e-s)/2;

      }

      return -1;

    }

 

 

1.  we find the value of mid,
2. Loop form start < end,

 

3. Condition 1. --- 

Check if the mid position  i.e. nums[mid] is our target or not,

If yes return the mid

4. Condition 2. ---

If the target in greater than nums[mid],

Move start to right side, i.e. start = mid + 1; 

5. Condition 3. ---

If the target in smaller than nums[mid],

Move end to left side, i.e. end = mid - 1;

 

3. Search.

We get the value of pivot from GETPIVOT, which divide the array into two parts.

Before call binary search, we check the target we are looking for exists in which line

L1 OR L2.

For this we can check whether,

nums[pivot] <= target && target <= nums[length-1]

 

i.e

If this condition satisfied that means the target exist in second Line L2.

Else , in First line L1.

 

Depending on that we call the bSearch with passing respective values.

 

If target exist in L1  we call Binary search for  0 index to pivot -1,

if target exist in L2  we call Binary search for  pivot index to length -1,

    int search (vector<int>& nums, int target) {

      int length = nums.size();

      int pivot = getPivot(nums, length);

      int ans;

      if(nums[pivot] <= target && target <= nums[length-1]){

        ans = bSearch(nums, pivot, length -1, target);

      }

      else {

        ans = bSearch(nums,0, pivot-1, target);

      }

      return ans;

    }

COMPLETE CODE

class Solution {

public:

    int getPivot(vector<int>& nums , int size){

        int s = 0, e= nums.size()-1, mid=s + (e -s)/2;

      while(s < e){

          if(nums[mid] >= nums[0]){

              s =mid+1;

          }

          else

            {e = mid;}

          mid=s + (e -s)/2;

      }

      return s;

    }

 

    int bSearch(vector<int>& nums, int s, int e , int target ){

      int mid = s+(e-s)/2;

      while(s<=e){

        if(nums[mid]== target)

          return mid;

        else if(nums[mid] < target)

          s = mid +1;

        else

          e = mid -1;

        mid = s+(e-s)/2;

      }

      return -1;

    }

 

    int search (vector<int>& nums, int target) {

      int length = nums.size();

      int pivot = getPivot(nums, length);

      int ans;

      if(nums[pivot] <= target && target <= nums[length-1]){

        ans = bSearch(nums, pivot, length -1, target);

      }

      else {

        ans = bSearch(nums,0, pivot-1, target);

      }

      return ans;

    }

};