LeetCode Day 19 - Search in Rotated Sorted Array

Subscribe for more educational videos on algorithms, coding interviews and competitive programming.

#Coding #Programming

[mariansoltan]

When I saw this problem, first thing that i remembered was you binary search lecture where you talked about that.

[jamjam]

Thanks so much. I finally understand it after several hours of studying

[AnkurDeka]

Totally loved your solution. I think the key idea was to understand that within the rotated array, by comparing any element with the first element we can determine which section the element belongs to. We could instead compare with the last element as well.

[domdom_hello]

Dude, you're the best! You help me a lot! I just love your style to explain things - so easy for me to understand, so clear. Thanks man!

[mohamadalibaydoun]

This was one of my Google interview questions 5 years ago. Aced it, got in

[vineethkumar]

@Errichto I watched your 'Binary Search Tutorial' and I could easily come up with optimal solution for this question. Thanks for your amazing videos

[PiyushKumar-qjue]

I used the first approach to solve it but I'm very pleased to learn another approach. Thanks ❤️

[SurajKumar-bwoi]

I ran both codes
Amazingly, both approach gives the same running time of 4 ms in Leetcode.

[Rekefa]

Can you do a data structures/ algorithm crash course? Would be a pleasure to learn from you

[CarrotCakeMake]

Wow, what a thing to see. I was just implementing a BTree data structure using circular buffers for children and data. An IRL version of this problem. Except I guess I know where the start of the circle is.

[usuyus]

I want to ask a question: because the question said that there wouldn't be any duplicates in the list, we didn't really consider examples like this:
[1, 1, 2, 4, 0, 1, 1, 1, 1, 1, 1]
4
In this case, we say m = 5 in the first iteration and encounter a 1 in nums[5]. Because we assume no duplicates, we think m is in the first sector while it actually is in the second one. This would cause the algorithm to not work. I have been thinking about the general case where duplicates are allowed and where we have to be able to also answer test cases like this, but couldn't actually find a feasible solution / modification to the existing solution. Any help is welcome as a comment :) (I have been looking for a solution for too long now... I really need help)

[mohamed]

good work! please keep doing these videos.

[neer]

Hey Errichto please tell the fine diff between (low+high)/2 and (low +(high-low)/2).

[hellowill]

Very cool! I think of it like the rotation partitions the array into two sorted parts.
E.g. [3, 4, 5, 0, 1, 2] = [3, 4, 5] ++ [0, 1, 2].
So if you're in the same part as target you're allowed to do standard binary search and if you're not in the same part then simply search that part with target in it.

[codeencode]

For the cases like this Eg: [5, 4, 3, 1, 2] . can the time complexity can log n instead of 3*logn ? Thanx Errichto

[aminela]

I can't understand why people react by dislike 😂BigUp anyway

[AshishSingh-dnwb]

Amazing explanation! Can you upload a video on Code Jam Round 1B maybe?

[thehalfblodprince]

why this problem passes in O(n) complexity?

[akhilanand]

code jam round 1 B solution please

[rajdave]

What is difference between low+high/2. And low +(high-low)/2 ?
Please tell