Search element in a circular sorted array

In this lesson, we will see how to perform binary search on a circular sorted array with distinct elements. This is a very famous programming interview question.
Tutorial Level: Intermediate
Prerequisite: Knowledge of binary search algorithm and basic programming

[wonderInNoWhere]

You are a legend. Even almost ten years later, your explanation is the best.

[AruneshSrivastava]

Before watching this, i watched 2 other videos on similar issue, dint understand a damm thing, then i just see this video's link on suggestions and i smiled . The complexity of the problem doesn't bother you if you have a good teacher. Thanks man

[excitingmonkey]

Man you are awesome! I was Leetcoding, got stuck in understanding the solution and searched for explanation. And here i am, mindblown by how simple you made me understand.

[RaoVenu]

Thanks for the great tutorial. My implementation (assuming we already have implementations for findRotations and binary search in place)

CircularArraySearch(A, n, x) {
lowIndex = findRotations(A, n) // Index of lowest value in circular sorted array O(lgN)
//Now we have two cases. The array to left of lowIndex is sorted. And the array to the right(including lowIndex is sorted)
if (x == A[lowIndex]) return lowIndex // O(c)
else if (x > A[lowIndex]) return BST(A, lowIndex + 1, n, x) // O(lgN)
else return BST(A, 0, lowIndex - 1, x) //O(lgN)
}

[S__Arslaan]

Amazing!!!No other youtube channel matches your level of explaination!!!!Thanks mycodeschool

[Aggarwal_Anshul]

Such an Efficient & Simple Solution to a tricky problem! Fantastic explanation BIG THANKS!

[Guillermorosales]

Thank you very much!!! for this series of videos, you explained it very well.

[StartDeutsch]

Hi! What do you use for writing? A tablet or what? Looks very good! Thank you

[Joyddep]

Exactly what I was looking for. Thank you for your excellent content!

[codingandmathvideos]

great tutorial! you simply rock!!! God bless you.
You probably should adjust the way you calculate the middle index. If you add 2 big positive numbers or 2 big negative numbers for that matter, you can get overflow.
Use mid = low + (high - low)/2 instead to get the index of the middle element.

[siddharthasharma]

as you mention that a circular sorted array with Distinct elements in description part of this problem, we can also skip equal sign- Array[mid] < Array[high] and same for Array[mid] > Array[low].

[yunususmani]

Can't thanks

You just saved my night :)

Thanks a lot :)

[SaumyaSharma]

Thank you so much....The evergreen lectures 🌟👌

[allanbee]

Hi,

Firstly, you are doing amazing job. Your teaching skills are superb!!

Can you please share your algorithm approach to print all the permutations of a string? String length could be any length.
e.g. abc, acb, bac, bca, cab, cba.

[nouralaaeldinmounirhashem]

Thanks for your great effort
You are an excellent teacher

[adityagupta]

Hey, thanks for this. It really helps. I want to just verify my approach is correct. How about we find the pivot using the previous tutorial, figure out which sorted array it belongs to (left of pivot or right of pivot) and apply binary search to whichever direction of pivot x belongs to? The time complexity is still 0 (log n), right?

[bhoopendrasharma]

Excellent tutorial, Thanks a ton.
I believe this will work for duplicates as well, especially for the example shown in the tutorial { 2, 2, 2, 2, 2, 0, 2, 2 }. I tried it and found working.

[jalajkhajotiaiitr]

Thanks for your work sir, it is really helpful

[bharathrajakumar]

Simple and easy to understand. Thank you !!!

[yuvarajravi]

Great tutorial. Other approach is just keep comparing first and last elements. Say if i=1, j=n-1, perform if a[i]<a[j], and i++, j-- and continue until you find the smallest element?