#8 Search in Rotated Sorted Array

#8 Search in Rotated Sorted Array

Blind 75. Array

Search in Rotated Sorted Array

Solved

There is an integer array nums sorted in ascending order (with distinct values).

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

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

Example 2:

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

In #7 Problem sorted array, we discussed in detail the importance of it.

Here i will quickly mention about it's gist.

Rotated Sorted Array is sorted array which is disrupted at pivotal point

RoratedSortedArray = [left Sorted Array , right sorted array]

where, each element in left sorted array is greater than right sorted array.

From finding minimum in rotated sorted array which is

function seven(nums){

  let l = 0; r = nums.length -1

  while( l <= r){

    let mid = Math.floor((l + r)/2 )

    if(nums[mid +1 ] < nums[mid]){

      return nums[mid + 1]

    }

    if(nums[l] <= nums[mid]){

      // we are left sorted array

      l = mid + 1

    }else{

      //we are at right sorted array

      r = mid -1

    }

  }

}

we can use this solution to come up with the index position to find a target

function searchInRotatedSearchArray(nums, target){

  let l = 0, r = nums.length -1

  while(l <= r){

    let mid = Math.floor((l + r) / 2)

    if(nums[mid] === target) return mid

    if(nums[l] <= nums[mid]){

      // we know we are in the left soted array

      // all the elements in the left sorted array is greater than right sorted array 

      // sorted meanns there are heavier number on the left hand side

      // here we we in the left sorted array

      // we cannot do a normal binary search so we do is, we need to see if the target is within the bound of 

      // left sorted array

      if (nums[l] <= target && target < nums[mid]) {

        r = mid -1

      }else{

        // we go search right sorted array

        l = mid + 1

      }

    }else{

      // we are on the right sorted array

      // similary we cannot do the normaly binary search,

      // so first check if the target is within the right sorted array

      if(nums[mid] < target && target <= nums[r]){

      l = mid + 1

      }else{

        // we need to go to left sorted array

        r = mid -1

      }

    }

  }

  return -1

}

this is how we can solve this