Dear readers, this is a very nice problem that is very similar to binary search. Let's understand the question first.

**Important Links :** Problem link, Solution Video

Pivot of Sorted Rotated Array

People don't care about what you say, they care about what you build.

~ Mark Zuckerberg

Pivot of Sorted Rotated Array

Dear readers, this is a very nice problem that is very similar to binary search. Let's understand the question first.

**Important Links :** Problem link, Solution Video

Problem Discussion :

- You are given an array(arr) of distinct integers, which is sorted and rotated around an unknown point.
- You have to find the smallest element.

Basically, if you plot the numbers, you will have to find the dip / lowest point.

If you have difficulty understanding the problem watch the video.

Approach :

For explanation, we will consider the array [10, 20, 30, 40, 50] but will look at all the possible shifts of the array.

We will initially have lo = 0 and hi = n-1 and mid will be (lo+hi)/2.

In all the previous scenarios you can see the arr[mid] < arr[high]. And quite clearly, the lowest value is always in the range [low, mid] both low and mid inclusive.

Whereas if you plot the same for other scenarios you will see.

arr[mid] > arr[high] which means there was a dip / lowest point between mid and high. In this case, the lowest point is clearly between [mid+1, high]. Why mid+1? Because we already know arr[mid] is greater than arr[high], so it's obvious that it is not the lowest point.

So, based on one condition we are separating the array into two halves.

Here n is odd, so one section is greater than the other.

Here n is even, so both the sections are equal in length.

If you didn't understand any part of this section watch the video.

Now, once we divide it into two sections we will choose one and keep doing the same process. Just like in Binary Search we would make a smaller section where we can find our target value. Here also we are divided into sections and will choose that section where we can find our minimum number.

Pseudo Code

lo = 0

hi = n-1

while lo is less than hi:

mid = (lo + hi)/2

if arr[mid] > arr[hi]

lo = mid + 1 // pivot lies in second half

else

hi = mid // pivot lies in first half

now lo == hi so we can return arr[lo] or arr[hi]

Taking hints from the pseudocode, try to write the actual code by yourself.

import java.io.*;
import java.util.*;
public class Main {
public static int findPivot(int[] arr) {
int lo = 0, hi = arr.length - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (arr[mid] > arr[hi]) {
lo = mid + 1;
} else {
hi = mid;
}
}
return arr[lo];
}
public static void main(String[] args) throws Exception {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scn.nextInt();
}
int pivot = findPivot(arr);
System.out.println(pivot);
}
}

java; true";

Analysis

Time Complexity :

**O(logn)**

Here every time the length of the array gets halved. Now if you have an array of length 8 how many times can you half it until it becomes an array of length 1. First, 8 can be halved to 4, then 2nd time if you half it, it will become 2 and then 3rd time it will become 1. So 3 times. Every time we are halving we are dividing the array and the log is nothing but repeated division. So, the number of times we can divide an array of length n will be log_{2}n. So time complexity is O(log_{2}n).

SPACE COMPLEXITY :

**O(1)**

No auxiliary arrays are used, hence the space complexity remains O(1) i.e constant.

Hopefully, you have understood the Algorithm. If you haven't understood properly I suggest you watch the full video and dry run the code by hand. That way you will understand the intuition behind this beautiful algorithm. All the best and keep learning!!