Search in Rotated Sorted Array
Vložit
- čas přidán 11. 10. 2021
- 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
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.
Exactly! I have been scratching my head for hours. This is the ONLY explanation which made sense
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.
most underrated explanation, thanks 😊
Wow ! Its Very easy after this video . Thanks Di
Awesome!!!
You are beyond imagination who can convert complex things into easy one.
one of the best explanations I've seen, thank you!
thank you so much. This is the best explanation on binary search in rotated sorted array.
very cool!
excellent explanation and ur making coding so nteresting, thank u very much
Minor comment on line 19 and 31. In the condition, it doesn't need to be (....
Amazing explaination ❤️
finally i understood here. thank you so much. 🙂
Thank you really understood
great expl
but how [1,3,5] is rotated array cause the pivote index is less than k
Did you do your schooling at AECS Kalpakkam.
Yes!
@@probabilitycodingisfunis1 You were of 2016 batch ..... I am junior of 2018 batch .... abhi bhi yaad hai u were the captain of the school..... very happy that ur sharing ur knowledge through utube...
@@omkarmandias8166 good old days!! AECS times were best!! thanks, wish you the best too !
mam everything is right but while running it is giving error;
int search(vector& nums, int target) {
int left =0;
int right =nums.size()-1;
int mid=left+(right-left)/2;
while(left
return -1 above the last } bracket
nice exp :)