Search in a Rotated Sorted Array (LeetCode 33) | Full solution with examples | Study Algorithms

You are required to return the index of a target element in a sorted rotated array. It is given that all the elements of the array are unique and we don't know how many times the array has been rotated. Watch this video to understand the problem statement and see what problems you might face with a conventional approach. I then work along with you to solve the problem in an efficient manner using a modified version of Binary Search. All along with visuals and explanations.

00:00 - Intro
00:55 - Problem Statement and description
02:34 - Brute Force Solution
04:11 - Method 1: Using Binary Search 2 times
06:41 - Method 2: Modified Binary Search
10:10 - Dry-run of Code
13:51 - Final Thoughts

📚 Links to topics I talk about in the video:

📖Reference Books:

My Recording Gear:

💻 Get Social 💻

#leetcode #programming #interview

[dobermanbruce]

When I need solution of any problem first I came and check if your video is present. You provide a greatExplanation. ThankYOu

[krishnavishwakarma]

Your explanation is really awesome bro. you are my goto person .. 👋

[Advaitare]

Amazing man! Your videos are easy to understand!

[hanumantkhandagale]

Great explanation.... thank you sir 👍😀

[NafisaParveen-gt]

thanks a lot sir, this explanation really helped a lot!!😄

[niteeshnayak]

class Solution {
public int search(int[] nums, int target) {

for(int i=0;i<nums.length;i++){
if(target == nums[i]){
return i;
}
}
return -1;
}
} solves in O(N)

[pulastyadas]

awesome sir.. pls continue other problems too.

[sumitpisal]

What happens when both the parts are sorted the serach may be directed to wrong direction when if block condition is being satisfied

[unemployedcse]

brute force solution is different and question is different, am I one who is finding this difference ?🤔 is it just searching element in array ?

[oppaivisuals]

My real question is
the question asks us to find the index of the target value and the target value is aready given in the question.. Cant we just do a normal search for the target value and pass the index of the target value?

[gautambafna]

On the 13th min, mid value will be 0+ (3-0)/2 = will be 1.

[chiruchiruchiranjeevi]

first of all sorry if you found this a silly 1, if the given arr is : [4, 5, 6, 7, 0, 1, 2] and target is 0; as per your code, in the main part of ELSE (arr[mid]<=target ---> from the given array going on the mid is 1 and target is 0, how is it even possible? as( 1<=0 ) is not TRUE, (&&) means both should be true right then how is it running please help me with this brother..

[infinite]

why you are using test cases please direct write the psvm code main fully to understadn and can run in intellij ide

[unknown-mfdd]

without recursion, simple solution
public int search(int[] nums, int target) {
int n = nums.length;
int left = 0;
int right = n-1;

while(left <= right) {
int mid = left + (right-left)/2;

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

// left sorted portion
if(nums[left] <= nums[mid]){
if(nums[left] <= target && target < nums[mid]){
right = mid-1;
}else{
left = mid +1;
}
}
//right sorted portion
else{
if(nums[mid] < target && target <= nums[right]){
left = mid + 1;
}else{
right = mid - 1;
}
}
}
return -1;
}

[Tech_Knowlege]

Bro 3/2 = 2. You are saying on 13.00 min ...ha haa 😂😂. You r wrong