Given an array of distinct elements which was initially sorted. This array may be rotated at some unknown point. The task is to find the minimum element in the given sorted and rotated array. 
Example 1:
Input:
N = 10
arr[] = {2,3,4,5,6,7,8,9,10,1}
Output: 1
Explanation: The array is rotated 
once anti-clockwise. So minimum 
element is at last index (n-1) 
which is 1.
Example 2:
Input:
N = 5
arr[] = {3,4,5,1,2}
Output: 1
Explanation: The array is rotated 
and the minimum element present is
at index (n-2) which is 1.
Your Task:
The task is to complete the function minNumber() which takes the array arr[] and its starting and ending indices (low and high) as inputs and returns the minimum element in the given sorted and rotated array.
Expected Time Complexity: O(LogN).
Expected Auxiliary Space: O(LogN).
Constraints:
1 <= N <= 10^{7}
1 <= arr[i] <= 10^{7}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Complete search

Starter code: #User function Template for python3





class Solution:

    

    #Function to find the minimum element in sorted and rotated array.

    def minNumber(self, arr,low,high):

        #Your code here

Solutions:
class Solution:

	def minNumber(self, arr, low, high):
		return min(arr)


class Solution:

	def minNumber(self, arr, low, high):
		if low > high:
			return -1
		if arr[low] <= arr[high]:
			return arr[low]
		while low <= high:
			mid = (low + high) // 2
			if arr[mid] > arr[mid + 1]:
				return arr[mid + 1]
			if arr[mid - 1] > arr[mid]:
				return arr[mid]
			if arr[mid] > arr[low]:
				low = mid + 1
			else:
				high = mid - 1
		return -1


class Solution:

	def minNumber(self, arr, low, high):
		min = arr[0]
		for i in range(0, len(arr)):
			if arr[i] < min:
				min = arr[i]
		return min


class Solution:

	def minNumber(self, arr, low, high):
		low = 0
		high = len(arr) - 1
		while low < high:
			middle = low + (high - low) // 2
			if arr[middle] > arr[high]:
				low = middle + 1
			elif high < low:
				high = low
			else:
				high -= 1
		return arr[low]


class Solution:

	def minNumber(self, arr, low, high):
		arr.sort()
		return arr[0]


class Solution:

	def minNumber(self, arr, low, high):
		m = arr[-1]
		for i in range(len(arr) - 2, -1, -1):
			if arr[i] < m:
				m = arr[i]
		return m


class Solution:

	def minNumber(self, arr, low, high):
		mini = arr[0]
		for i in range(1, len(arr)):
			if mini > arr[i]:
				mini = arr[i]
		return mini


class Solution:

	def minNumber(self, arr, l, h):
		n = len(arr)
		while l < h:
			mid = (l + h) // 2
			if arr[mid] > arr[h]:
				l = mid + 1
			else:
				h = mid
		return arr[l]


class Solution:

	def minNumber(self, arr, low, high):
		if low == high:
			return arr[low]
		elif arr[high] < arr[high - 1]:
			return arr[high]
		left = low + 1
		right = high - 1
		while left <= high:
			mid = (left + right) // 2
			if arr[mid] < arr[mid + 1] and arr[mid] < arr[mid - 1]:
				return arr[mid]
			elif arr[mid] > arr[high]:
				left = mid + 1
			else:
				right = mid - 1
		return arr[low]


class Solution:

	def minNumber(self, arr, low, high):
		if len(arr) <= 2:
			min(arr)
		if arr[low] < arr[high]:
			return arr[low]
		while low <= high:
			mid = (low + high) // 2
			if mid < len(arr) - 1 and arr[mid] > arr[mid + 1]:
				return arr[mid + 1]
			elif arr[mid] < arr[mid - 1]:
				return arr[mid]
			elif arr[mid] > arr[low]:
				low = mid + 1
			else:
				high = mid - 1


def pivot(arr):
	(st, en) = (0, len(arr) - 1)
	while st <= en:
		mid = (st + en) // 2
		if mid < len(arr) - 1 and arr[mid] > arr[mid + 1]:
			return mid
		if mid > 0 and arr[mid - 1] > arr[mid]:
			return mid - 1
		if arr[st] >= arr[mid]:
			en = mid - 1
		else:
			st = mid + 1

class Solution:

	def minNumber(self, arr, low, high):
		piv = pivot(arr)
		if piv == None:
			return arr[0]
		return min(arr[0], arr[piv + 1])


class Solution:

	def minNumber(self, arr, low, high):
		minimum = 0
		mini = 10 ** 7
		i = len(arr) - 1
		while i >= 0:
			minimum = arr[i]
			if mini > minimum:
				mini = minimum
				i -= 1
			else:
				i -= 1
		return mini


class Solution:

	def minNumber(self, arr, low, high):
		x = arr[0]
		count = 0
		for i in arr:
			if i < x:
				count = count + 1
		return arr[-count]


class Solution:

	def minNumber(self, arr, low, high):
		if arr[low] < arr[high]:
			return arr[low]
		mid = (low + high) // 2
		i = 0
		j = 0
		smallest = 0
		if arr[low] < arr[mid]:
			smallest = arr[0]
			i = mid
			j = high + 1
		else:
			smallest = arr[mid]
			i = 0
			j = mid
		for k in range(i, j):
			if arr[k] < smallest:
				smallest = arr[k]
		return smallest


import math

class Solution:

	def minNumber(self, arr, low, high):
		res = arr[low]
		for i in range(low + 1, high + 1):
			if arr[i] < res:
				res = min(res, arr[i])
		return res


class Solution:

	def minNumber(self, arr, low, high):
		start = 0
		end = len(arr) - 1
		while start <= end:
			mid = int((start + end) / 2)
			if arr[start] <= arr[end]:
				return arr[start]
			if arr[mid] < arr[start]:
				end = mid
			elif arr[mid] > arr[end]:
				start = mid + 1
		return -1


class Solution:

	def minNumber(self, arr, low, high):
		import math
		low = 0
		high = len(arr) - 1
		while low <= high:
			mid = int((low + high) / 2)
			if arr[low] <= arr[high]:
				return arr[low]
			if arr[mid] > arr[high]:
				low = mid + 1
			elif arr[mid] < arr[low]:
				high = mid
		return -1


class Solution:

	def minNumber(self, arr, low, high):
		for i in range(high, -1, -1):
			if arr[i] < arr[i - 1]:
				return arr[i]


class Solution:

	def minNumber(self, a, l, h):
		ans = 1000000000
		if a[0] < a[-1]:
			return a[0]
		while l <= h:
			mid = (l + h) // 2
			if a[mid] >= a[0]:
				l = mid + 1
			else:
				h = mid - 1
				ans = mid
		return a[ans]


class Solution:

	def minNumber(self, arr, low, high):
		mini = float('inf')
		while low <= high:
			if arr[low] < arr[high]:
				mini = min(mini, arr[low])
				break
			m = low + (high - low) // 2
			mini = min(mini, arr[m])
			if arr[low] <= arr[m]:
				low = m + 1
			else:
				high = m - 1
		return mini


class Solution:

	def minNumber(self, arr, low, high):
		arr.sort()
		m = arr.pop(0)
		return m


class Solution:

	def minNumber(self, arr, low, high):
		if arr[low] < arr[high]:
			return arr[low]
		n = high + 1
		while low <= high:
			mid = (low + high) // 2
			prev = (mid + n - 1) % n
			nex = (mid + 1) % n
			if arr[mid] < arr[prev] and arr[mid] < arr[nex]:
				return arr[mid]
			elif arr[mid] > arr[0]:
				low = mid + 1
			elif arr[mid] < arr[n - 1]:
				high = mid - 1
		return arr[mid]


class Solution:

	def minNumber(self, arr, low, high):
		mini = arr[0]
		while low <= high:
			mid = (low + high) // 2
			if arr[mid] < arr[0]:
				mini = min(mini, arr[mid])
				high = mid - 1
			else:
				low = mid + 1
		return mini


class Solution:

	def minNumber(self, arr, low, high):
		st = 0
		end = len(arr) - 1
		min_el = arr[0]
		while end - st > 1:
			mid = (end + st) // 2
			if arr[end] > arr[st]:
				return arr[st]
			if arr[mid] < arr[st]:
				end = mid
			else:
				st = mid + 1
		return min(arr[end], arr[st])


class Solution:

	def minNumber(self, arr, low, high):
		middle = len(arr) // 2
		minE = arr[middle]
		if arr[middle] > arr[0] and arr[middle] > arr[-1]:
			for i in range(middle, len(arr)):
				if minE > arr[i]:
					minE = arr[i]
		else:
			for i in range(middle + 1):
				if minE > arr[i]:
					minE = arr[i]
		return minE


class Solution:

	def minNumber(self, arr, low, high):
		mine = 99999999999
		while low <= high:
			mid = (low + high) // 2
			if arr[low] <= arr[mid]:
				mine = min(mine, arr[low])
				low = mid + 1
			else:
				mine = min(mine, arr[mid])
				high = mid - 1
		return mine


class Solution:

	def minNumber(self, arr, low, high):
		d = float('inf')
		for i in range(len(arr)):
			if arr[i] < d:
				d = arr[i]
		return d


class Solution:

	def minNumber(self, arr, l, h):
		if arr[l] <= arr[h]:
			return arr[l]
		while l <= h:
			m = (l + h) // 2
			if arr[m] >= arr[0]:
				l = m + 1
			else:
				h = m - 1
		return arr[l]


class Solution:

	def minNumber(self, arr, low, high):
		s = 0
		e = len(arr) - 1
		while s < e:
			mid = s + (e - s) // 2
			if arr[mid] < arr[e]:
				e = mid
			else:
				s = mid + 1
		return arr[e]


class Solution:

	def minNumber(self, arr, low, high):
		if low == high:
			return arr[0]
		elif arr[low] < arr[high]:
			return arr[low]
		ans = 0
		while low <= high:
			mid = (low + high) // 2
			if arr[mid] > arr[mid + 1]:
				ans = mid + 1
				break
			elif arr[mid] < arr[mid - 1]:
				ans = mid
				break
			elif arr[mid] > arr[0]:
				low = mid + 1
			else:
				high = mid - 1
		return arr[ans]


class Solution:

	def minNumber(self, arr, low, high):
		l = 0
		r = len(arr) - 1
		ans = -1
		while l <= r:
			mid = (l + r) // 2
			if arr[mid] <= arr[-1]:
				ans = arr[mid]
				r = mid - 1
			else:
				l = mid + 1
		return ans


class Solution:

	def minNumber(self, arr, low, high):
		mini = 10000000
		while low <= high:
			mini = min(arr[low], arr[high], mini)
			if arr[low] > arr[high]:
				low += 1
			else:
				high -= 1
		return mini


class Solution:

	def minNumber(self, arr, low, high):
		begin = low
		end = high
		if arr[begin] > arr[end]:
			while begin < end:
				m = (begin + end) // 2
				if arr[m] >= arr[0]:
					begin = m + 1
				else:
					end = m
		return arr[begin]


class Solution:

	def minNumber(self, arr, low, high):
		i = len(arr) - 1
		while i > 0:
			if arr[i] < arr[i - 1]:
				return arr[i]
			i -= 1
		return arr[0]


class Solution:

	def minNumber(self, arr, l, h):
		if arr[0] < arr[-1]:
			return arr[0]
		return min(arr)


class Solution:

	def minNumber(self, arr, low, high):
		min_val = 10000001
		for i in range(high, low - 1, -1):
			if arr[i] < min_val:
				min_val = arr[i]
			else:
				return min_val
		return min_val


class Solution:

	def minNumber(self, arr, low, high):
		low = 0
		high = len(arr) - 1
		n = len(arr)
		while low <= high:
			mid = low + (high - low) // 2
			next = (mid + 1) % n
			prev = (mid - 1 + n) % n
			if arr[mid] >= arr[next]:
				return arr[next]
			if arr[mid] <= arr[prev]:
				return arr[mid]
			if arr[mid] >= arr[low]:
				low = mid + 1
			elif arr[mid] <= arr[high]:
				high = mid - 1


class Solution:

	def minNumber(self, arr, low, high):
		n = len(arr)
		count = 0
		while low <= high:
			mid = (low + high) // 2
			if mid - 1 >= 0 and mid + 1 < n and (arr[mid] < arr[mid - 1]) and (arr[mid + 1] > arr[mid]):
				return arr[mid]
			elif mid - 1 < 0 and mid + 1 < n and (arr[mid + 1] > arr[mid]):
				return arr[mid]
			elif mid - 1 >= 0 and mid + 1 >= n and (arr[mid - 1] > arr[mid]):
				return arr[mid]
			elif mid + 1 < n and arr[mid] > arr[mid + 1]:
				return arr[mid + 1]
			elif arr[low] > arr[high] and arr[mid] > arr[high] and (arr[mid] > arr[low]):
				low = mid + 1
			elif arr[mid] < arr[high] and arr[low] > arr[high]:
				high = mid - 1
			elif arr[low] < arr[high] < arr[mid]:
				high = mid - 1
			elif arr[low] < arr[mid] < arr[high]:
				high = mid - 1


class Solution:

	def minNumber(self, arr, low, high):
		n = len(arr)
		left = low
		right = high
		while left < right:
			mid = (left + right) // 2
			if arr[mid] > arr[right]:
				left = mid + 1
			else:
				right = mid
		return arr[left]


class Solution:

	def minNumber(self, arr, low, high):
		l = 0
		h = len(arr) - 1
		if arr[l] < arr[h]:
			return arr[l]
		while l <= h:
			mid = (l + h) // 2
			if arr[mid] < arr[l]:
				h = mid - 1
			elif arr[mid + 1] < arr[mid]:
				return arr[mid + 1]
			else:
				l = mid + 1
		return -1


class Solution:

	def minNumber(self, arr, low, high):
		n = len(arr)
		while low <= high:
			mid = low + (high - low) // 2
			pre = (mid - 1 + n) % n
			nxt = (mid + 1) % n
			if arr[mid] <= arr[pre] and arr[mid] <= arr[nxt]:
				return arr[mid]
			elif arr[mid] < arr[high]:
				high = mid - 1
			else:
				low = mid + 1