I have Already covered Arrays and Binary search basics till now. So I will spend some time today going over some problems on Binary search and one Array question to stay on track.

So let’s start

Q1. Find Pivot element in a Rotated Sorted Array

Question link: <To be updated>

Thought Process

For every Binary Search Question our main objective is to reduce the search space based on a particular condition. Each iteration reduces the search space till we get to our desired Target index. After which the condition becomes false and we exit the search process.

First thought which pops up is to see on which side of the target are the elements increasing or decreasing which clearly doesn’t help here. So let focus on our target Element

The target element has a special property that arr[target]<arr[target-1]

So we use this Condition to see if we have to move the start pointer or the end pointer, but we get stuck because in the left and right of the element both will return False for the given condition

Let’s read the question again. The array has a property that its a SORTED rotated array.

Let’s take up a test case and analyze

Test case: [11,12,2,3,4,5]

We observe that the last element will always be smaller than 1st element

From here we get the condition that All the element Left of the pivot will be greater than the first element and on the right will be less than the first element

So if we are on the left Branch we will Move our start pointer to mid+1 index and end to mid

Q- Why end = mid and not mid-1?

consider a case where mid the required element but the search space hasn’t been reduced so we have to proceed to next iteration. if we do end=mid-1 we will loose the solution

To answer this let’s consider the worst case :