I did not Quite understand His Concept. THe part that I did not understand is where he told us to take parts and then I got lost. after taking parts, what to do next?
Can Someone Explain me how this works
hello @JaveedYara
Let’s take some examples and see how we can simplify the condition.
Original sorted array
[1, 2, 3, 4, 5, 6, 7]
After rotation, it might be something like
[3, 4, 5, 6, 7, 1, 2]
[6, 7, 1, 2, 3, 4, 5]
[1, 2, 3, 4, 5, 6, 7] <-- rotated and end up the same
and etc…
When you divide the rotated array into two halves, using mid index, at least one of subarray should remain sorted ALWAYS .
[3, 4, 5, 6, 7, 1, 2]
-> [3, 4, 5] [ 6, 7, 1, 2]
the left side remains sorted
[6, 7, 1, 2, 3, 4, 5]
-> [6, 7, 1] [2, 3, 4, 5]
the right side remains sorted
[1, 2, 3, 4, 5, 6, 7]
-> [1, 2, 3] [4, 5, 6, 7]
Both sides remain sorted.
If you know one side is sorted, the rest of logic becomes very simple.
If one side is sorted, check if the target is in the boundary, otherwise it’s on the other side.
IF smallest <= target <= biggest
then target is here
ELSE
then target is on the other side
okay sure. I will try
okay sure. I will try for sure