# Problem Statement :

Sample Input:

`N = 4Arr = {3 4 1 2}`

Output:

`1`

# Optimized Approach

1. We start by making two variables named low and high, where low = 0 and high = n-1. Now we run a loop that will run till low <= high. We also make another variable mid, which is equal to (low+high)/2.
2. Now we make 4 cases and accordingly solve our problem.
3. Case 1: arr[low] <= arr[high]
• We return arr[low] since the array is sorted, arr[low] will be the minimum element.

4. Now we make a variable named next which will be equal to (mid+1)%n and previous which will be equal to (mid+n-1)%n.

5. Case 2: (arr[mid] <= arr[next]) and (arr[mid] <= arr[previous])

• We return arr[mid]. We do this because on observing we can see that only the minimum element will have this special property where it is smaller than both of its neighbours. Example 4 1 2 3, here you can see that only 1, which is the minimum element, in this case, is the element that is smaller than both of its neighbours 4 and 2.

6. Case 3: arr[mid] <= arr[high]

• Here we see that if the current middle element is less than the current high element, that means the minimum element won’t be present in the right half of the array(with reference to mid). Hence we discard this search space and make high = mid-1.

7. Case 4: arr[mid] >= arr[low]

• This case is similar to Case 3, the only difference is that here we can observe that if our current middle element is greater than the current lower element, the minimum element won’t be present in the left half of the array(with reference to mid). Hence we discard this search space and make low = mid+1.

Time Complexity: O(log(N))
Space Complexity: O(1)