Search in Rotated Sorted Array #Binary Search Rotations Leetcode 33.

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

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

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
Example 3:

Input: nums = [1], target = 0
Output: -1

[koushalnmusic]

EVERY ELEMENT IS EITHER LEFT SORTED OR RIGHT SORTED !! this explanation made it easy for me to understand the algorithm, Thanks a lot for all the work you've been putting into making these videos.

[tanim]

most underrated explanation, thanks 😊

[sunwoodad]

Minor comment on line 19 and 31. In the condition, it doesn't need to be (....<= nums[mid]) or (nums[mid]<=....) because nums[mid] should not be the target at this point.

[opsumon]

Wow ! Its Very easy after this video . Thanks Di

[shatrudhankumar]

Awesome!!!
You are beyond imagination who can convert complex things into easy one.

[chintamanipala]

every array have 2 part either left sorted or right sorted. first we need to check it if left side part is sorted and if the target value is lies between that range that means we have to eliminate the right side otherwise we have to eliminate left side . this part is clear my whole doubt. thanks mam for making this video.

[poojapawar-si]

thank you so much. This is the best explanation on binary search in rotated sorted array.

[RockStar-Siblings]

excellent explanation and ur making coding so nteresting, thank u very much

[oneandonlyflow]

one of the best explanations I've seen, thank you!

[sushmitakumari]

finally i understood here. thank you so much. 🙂

[omkarmandias]

Did you do your schooling at AECS Kalpakkam.

[kushalshukla]

but how [1, 3, 5] is rotated array cause the pivote index is less than k

[RishabhSharma-tprs]

mam everything is right but while running it is giving error;

int search(vector<int>& nums, int target) {
int left =0;
int right =nums.size()-1;
int mid=left+(right-left)/2;
while(left<=right){
if(nums[mid]==target){
return mid;
}
if(nums[left]<=nums[mid]){

right=mid-1;}

else{
left=mid+1;}


}
else{

left=mid+1; }
else{
right=mid-1;}

}
}

return -1;

please tell me mam where it is wrong