A sorted(in ascending order) array A[ ] with distinct elements is rotated at some unknown point, the task is to find the minimum element in it.
Example 1
Input:
N = 5
arr[] = {4 ,5 ,1 ,2 ,3}
Output: 1
Explanation: 1 is the minimum element inthe array.
Example 2
Input:
N = 7
arr[] = {10, 20, 30, 40, 50, 5, 7}
Output: 5
Explanation: Here 5 is the minimum element.
 
Your Task:
Complete the function findMin() which takes an array arr[] and n, size of the array as input parameters, and returns the minimum element of the array.
Expected Time Complexity: O(log N).
Expected Auxiliary Space: O(log N).
Constraints:
1 ≤ N ≤ 100000
1 ≤ A[i] ≤ 1000000

Source: geeksforgeeks | Difficulty: EASY
Tags: Complete search

Starter code: #User function Template for python3



class Solution:

    def findMin(self, arr, n):

        #complete the function here

Solutions:
class Solution:

	def findMin(self, arr, n):
		return min(arr)


import sys

class Solution:

	def findMin(self, arr, n):
		mini = sys.maxsize
		for i in arr:
			if i < mini:
				mini = i
		return mini


class Solution:

	def findMin(self, arr, n):
		smallest_number = arr[0]
		for number in range(n):
			if arr[number] < smallest_number:
				smallest_number = arr[number]
		return smallest_number


class Solution:

	def findMin(self, arr, n):
		(start, end) = (0, n - 1)
		while start < end:
			mid = start + (end - start) // 2
			if arr[mid] > arr[end]:
				start = mid + 1
			else:
				end = mid
		return arr[start]


class Solution:

	def findMin(self, arr, n):
		i = 0
		j = n - 1
		if arr[0] < arr[j]:
			return arr[0]
		while i <= j:
			mid = (i + j) // 2
			if arr[mid] < arr[mid - 1]:
				return arr[mid]
			if arr[mid] > arr[0]:
				i = mid + 1
			else:
				j = mid


class Solution:

	def findMin(self, A, n):
		min = A[0]
		l = 0
		h = n - 1
		while l <= h:
			mid = (l + h) // 2
			if A[mid] < min:
				min = A[mid]
			elif A[mid] >= A[l] and A[mid] >= A[h]:
				l = mid + 1
			else:
				h = mid - 1
		return min


class Solution:

	def findMin(self, arr, n):

		def findMinUtil(arr, start, end, minimum):
			if end == start:
				return min(minimum, arr[start])
			elif end - start <= 1:
				return min(minimum, arr[start], arr[end])
			mid = (start + end) // 2
			if arr[mid] > arr[start]:
				minimum = min(minimum, findMinUtil(arr, mid + 1, end, minimum), arr[start])
			else:
				minimum = min(minimum, findMinUtil(arr, start, mid, minimum), arr[mid + 1])
			return minimum
		return findMinUtil(arr, 0, n - 1, float('inf'))


class Solution:

	def findMin(self, arr, n):
		(lo, hi) = (0, n - 1)
		while lo < hi:
			mid = (lo + hi) // 2
			if arr[mid] < arr[hi]:
				hi = mid
			else:
				lo = mid + 1
		return arr[lo]


class Solution:

	def findMin(self, arr, n):
		(l, r) = (0, n - 1)
		while l <= r:
			mid = l + (r - l) // 2
			if mid == 0 or arr[mid - 1] > arr[mid]:
				return arr[mid]
			elif arr[mid] < arr[l]:
				r = mid - 1
			elif arr[mid] > arr[r]:
				l = mid + 1
			else:
				return arr[l]
		return -1


class Solution:

	def findMin(self, arr, n):
		start = 0
		end = len(arr) - 1
		while start < end:
			middle = start + (end - start) // 2
			if arr[middle] > arr[end]:
				start = middle + 1
			elif arr[middle] < arr[end]:
				end = middle
			else:
				end -= 1
		return arr[start]


class Solution:

	def findMin(self, arr, n):
		arr.sort()
		return arr[0]


class Solution:

	def findMin(self, arr, n):
		left = 0
		right = n - 1
		while left <= right:
			mid = (left + right) // 2
			previous = (mid - 1) % n
			next1 = (mid + 1) % n
			if arr[mid] <= arr[previous] and arr[mid] <= arr[next1]:
				return arr[mid]
			if arr[mid] <= arr[right]:
				right = mid - 1
			elif arr[left] <= arr[mid]:
				left = mid + 1


class Solution:

	def findMin(self, arr, n):
		res = arr[0]
		l = 0
		h = len(arr) - 1
		while l <= h:
			if arr[l] < arr[h]:
				res = min(res, arr[l])
				break
			mid = (l + h) // 2
			res = min(res, arr[mid])
			if arr[mid] >= arr[l]:
				l = mid + 1
			else:
				h = mid - 1
		return res


import heapq

class Solution:

	def findMin(self, arr, n):
		(left, right) = (0, n - 1)
		while left <= right:
			mid = (left + right) // 2
			prev = (mid - 1) % n
			next = (mid + 1) % n
			if arr[mid] <= arr[prev] and arr[mid] <= arr[next]:
				return arr[mid]
			elif arr[mid] <= arr[right]:
				right = mid - 1
			elif arr[mid] >= arr[left]:
				left = mid + 1


import heapq

class Solution:

	def findMin(self, arr, n):
		return heapq.nsmallest(1, arr)[0]


class Solution:

	def findMin(self, nums, n):
		if len(nums) is 1:
			return nums[0]
		leftSmaller = True if nums[0] < nums[-1] else False
		if leftSmaller:
			return nums[0]
		if len(nums) is 2:
			return min(nums)
		start = 0
		end = len(nums) - 1
		while start <= end:
			mid = (start + end) // 2
			if nums[mid] < nums[mid - 1]:
				return nums[mid]
			elif nums[mid] < nums[end]:
				end = mid - 1
			else:
				start = mid + 1
		return 0


class Solution:

	def findMin(self, arr, n):
		first = 0
		end = n - 1
		if arr[first] < arr[end]:
			return arr[first]
		while first < end:
			mid = (first + end) // 2
			if arr[mid] > arr[mid + 1]:
				return arr[mid + 1]
			elif arr[mid] < arr[first]:
				end = mid
			else:
				first = mid


class Solution:

	def findMin(self, arr, n):
		left = 0
		right = n - 1
		if arr[left] < arr[right]:
			return arr[left]
		while left < right:
			mid = (left + right) // 2
			if arr[mid] > arr[mid + 1]:
				return arr[mid + 1]
			elif arr[mid] < arr[left]:
				right = mid
			else:
				left = mid


class Solution:

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


class Solution:

	def findMin(self, nums, n):
		(left, right) = (0, n - 1)
		if n <= 1 or nums[left] < nums[right]:
			return nums[left]
		while left < right:
			mid = (left + right) // 2
			(prev, curr, next) = (nums[mid - 1], nums[mid], nums[mid + 1])
			if curr > next:
				return next
			if prev > curr:
				return curr
			if nums[0] < curr:
				left = mid + 1
			else:
				right = mid - 1


class Solution:

	def findMin(self, arr, n):
		min = arr[0]
		for i in range(n):
			if arr[i] < min:
				min = arr[i]
		return min


class Solution:

	def findMin(self, arr, n):
		min1 = 100000
		i = 0
		j = n - 1
		while i <= j:
			if arr[i] < arr[j]:
				min1 = min(arr[i], min1)
				break
			mid = int(i + (j - i) / 2)
			if arr[i] <= arr[mid]:
				min1 = min(min1, arr[i])
				i = mid + 1
			else:
				min1 = min(min1, arr[mid])
				j = mid - 1
		return min1


class Solution:

	def findMin(self, arr, n):
		l = 0
		r = n - 1
		while l <= r:
			mid = (l + r) // 2
			if arr[l] <= arr[mid] and arr[mid] <= arr[r]:
				return arr[l]
			elif arr[r] >= arr[mid] and arr[mid] >= arr[l]:
				return arr[r]
			elif r - l == 1:
				return min(arr[r], arr[l])
			elif arr[l] < arr[mid]:
				l = mid
			elif arr[mid] < arr[r]:
				r = mid


class Solution:

	def findMin(self, arr, n):
		m = arr[-1]
		for i in range(n - 2, -1, -1):
			if arr[i] < m:
				m = arr[i]
		return m


class Solution:

	def findMin(self, arr, n):
		v = sorted(arr)
		return min(v)


class Solution:

	def findMin(self, arr, n):
		(low, high) = (0, n)
		while low < high:
			mid = (low + high) // 2
			if arr[0] <= arr[mid]:
				low = mid + 1
			else:
				high = mid
		if low == n:
			low = 0
		return arr[low]


class Solution:

	def findMin(self, arr, n):
		arr.sort()
		res = min(arr)
		return res


import sys
intmax = sys.maxsize

class Solution:

	def findMin(self, arr, n):
		l = 0
		r = n - 1
		while l <= r:
			mid = (l + r) // 2
			if arr[l] >= arr[mid] and arr[mid] >= arr[r]:
				return arr[r]
			if mid == 0 or arr[mid - 1] > arr[mid]:
				return arr[mid]
			if arr[mid] < arr[l]:
				r = mid - 1
			elif arr[mid] > arr[r]:
				l = mid + 1
			else:
				return arr[l]
		return -1


import sys
intmax = sys.maxsize

class Solution:

	def findMin(self, arr, n):
		t = intmax
		p = -1
		for i in range(n):
			if arr[i] <= t:
				t = arr[i]
				p = i
		return t


import sys

class Solution:

	def findMin(self, arr, n):
		low = 0
		high = n - 1
		minVal = sys.maxsize
		while low <= high:
			mid = (low + high) // 2
			if arr[low] <= arr[high]:
				minVal = min(minVal, arr[low])
				break
			elif arr[low] <= arr[mid]:
				minVal = min(minVal, arr[low])
				low = mid + 1
			else:
				minVal = min(minVal, arr[mid])
				high = mid - 1
		return minVal


class Solution:

	def findMin(self, nums, n):
		low = 0
		high = n - 1
		while low < high:
			mid = low + high >> 1
			if nums[mid] > nums[high]:
				low = mid + 1
			else:
				high = mid
		return nums[low]


class Solution:

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


class Solution:

	def findMin(self, arr, n):
		(left, right) = (0, n - 1)
		ans = arr[left]
		while left <= right:
			if arr[left] < arr[right]:
				return min(ans, arr[left])
				break
			mid = (left + right) // 2
			ans = min(ans, arr[mid])
			if arr[left] <= arr[mid]:
				left = mid + 1
			else:
				right = mid - 1
		return ans


class Solution:

	def findMin(self, nums, n):
		high = len(nums) - 1
		low = 0
		ans = 999999
		while high >= low:
			mid = (low + high) // 2
			if nums[mid] < ans:
				ans = nums[mid]
			if nums[low] < nums[mid] and nums[mid] < nums[high]:
				if nums[low] < nums[high]:
					high = mid - 1
				else:
					low = mid + 1
			elif nums[mid] >= nums[low]:
				low = mid + 1
			else:
				high = mid - 1
		return ans


class Solution:

	def findMin(self, arr, n):
		for i in range(1, len(arr)):
			if arr[i] < arr[i - 1]:
				return arr[i]
		return arr[0]


class Solution:

	def findMin(self, arr, n):
		first = 0
		last = len(arr) - 1
		while first < last:
			mid = (first + last) // 2
			if arr[mid] < arr[last]:
				last = mid
			else:
				first = mid + 1
		return arr[first]


import math

class Solution:

	def findMin(self, a, n):
		beg = 0
		end = n - 1
		min_ele = float('inf')
		while beg < end:
			min_ele = min(min_ele, a[beg])
			mid = math.ceil((beg + end) / 2.0)
			if a[beg] < a[mid]:
				beg = mid + 1
			else:
				min_ele = min(min_ele, a[mid])
				end = mid - 1
		min_ele = min(min_ele, a[end])
		return min_ele


class Solution:

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


class Solution:

	def findMin(self, arr, n):
		left = 0
		right = n - 1
		minVal = float('inf')
		while left <= right:
			if arr[left] <= arr[right]:
				minVal = min(minVal, arr[left])
				break
			mid = (left + right) // 2
			if arr[left] <= arr[mid] and arr[left] >= arr[right]:
				left = mid + 1
			elif arr[mid] <= arr[left] and arr[mid] <= arr[right]:
				minVal = min(minVal, arr[mid])
				right = mid - 1
			else:
				right = mid
		return minVal


class Solution:

	def findMin(self, nums, n):
		n = len(nums)
		(s, e) = (0, n - 1)
		while s < e:
			mid = s + e >> 1
			if nums[s] <= nums[e]:
				return nums[s]
			if nums[mid] >= nums[s]:
				s = mid + 1
			else:
				e = mid
		return nums[s]


import numpy as np

class Solution:

	def findMin(self, arr, n):
		arr = np.array(arr)
		return np.min(arr)


class Solution:

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