Given a sorted and rotated array A of N elements which is rotated at some point, and may contain duplicates and given an element key. Check whether the key exist in the array A or not.
Example 1:
Input:
N = 7
A[] = {2,5,6,0,0,1,2}
key = 0
Output:
1
Explanation:
0 is found at index 3.
Example 2:
Input:
N = 7
A[] = {2,5,6,0,0,1,2}
key = 3
Output:
0
Explanation:
There is no element that has value 3.
Your Task:
Complete the function search() which takes a integer N and  an array A and the Key as input parameters, and returns the answer.
Expected Time Complexity: O(log N).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 5000
0 ≤ A[i] ≤ 108
1 ≤ key ≤ 108

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def Search(self, n, arr, k):

        # code here

Solutions:
class Solution:

	def Search(self, n, arr, k):
		if k in arr:
			return 1
		else:
			return 0


class Solution:

	def Search(self, n, arr, k):
		for i in range(len(arr)):
			if arr[i] == k:
				return 1
		return 0


class Solution:

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


class Solution:

	def Search(self, n, arr, k):
		i = 0
		j = n - 1
		while i <= j:
			mid = i + j >> 1
			if arr[mid] == k:
				return 1
			elif arr[i] == k:
				return 1
			elif arr[j] == k:
				return 1
			elif arr[i] == arr[mid] == arr[j]:
				i += 1
				j -= 1
			elif arr[i] < arr[mid]:
				if arr[i] <= k and k <= arr[mid]:
					j = mid - 1
				else:
					i = mid + 1
			elif arr[mid] <= k and k <= arr[j]:
				i = mid + 1
			else:
				j = mid - 1
		return 0


class Solution(object):

	def Search(self, n, nums, target):
		(left, right) = (0, n - 1)
		while left <= right:
			mid = (left + right) // 2
			curr = nums[mid]
			if curr == target:
				return 1
			elif nums[left] == curr == nums[right]:
				left += 1
				right -= 1
			elif nums[left] <= curr:
				if nums[left] <= target < curr:
					right = mid - 1
				else:
					left = mid + 1
			elif curr < target <= nums[right]:
				left = mid + 1
			else:
				right = mid - 1
		return 0


class Solution:

	def Search(self, n, a, key):
		low = 0
		high = n - 1
		while low <= high:
			mid = low + (high - low) // 2
			if a[mid] == k:
				return 1
			if a[mid] == a[low]:
				low += 1
				continue
			if a[mid] == a[high]:
				high -= 1
				continue
			if a[low] < a[mid]:
				if k >= a[low] and k < a[mid]:
					high = mid - 1
				else:
					low = mid + 1
			elif k > a[mid] and k <= a[high]:
				low = mid + 1
			else:
				high = mid - 1
		return 0


class Solution:

	def Search(self, n, arr, k):
		l = 0
		u = n - 1
		while l <= u:
			while l < u and arr[l] == arr[l + 1]:
				l += 1
			while l < u and arr[u] == arr[u - 1]:
				u -= 1
			mid = l + u >> 1
			if arr[mid] == k:
				return 1
			elif arr[l] <= arr[mid]:
				if arr[l] <= k and arr[mid] >= k:
					u = mid - 1
				else:
					l = mid + 1
			elif arr[u] >= k and arr[mid] <= k:
				l = mid + 1
			else:
				u = mid - 1
		return 0


class Solution:

	def Search(self, n, arr, k):
		(lo, hi) = (0, n - 1)
		while lo <= hi:
			if hi - lo <= 5:
				return 1 if k in arr[lo:hi + 1] else 0
			mid = (lo + hi) // 2
			if arr[mid] == k or arr[lo] == k or arr[hi] == k:
				return 1
			elif arr[lo] == arr[hi] and arr[lo] == arr[mid]:
				lo += 1
				hi -= 1
			elif arr[lo] < arr[mid] or (arr[lo] == arr[mid] and arr[mid] > arr[hi]):
				if arr[lo] < k and k < arr[mid]:
					hi = mid - 1
				else:
					lo = mid + 1
			elif arr[hi] >= arr[mid] or (arr[hi] == arr[mid] and arr[mid] < arr[lo]):
				if arr[mid] < k and k < arr[hi]:
					lo = mid + 1
				else:
					hi = mid + 1
		return 0


class Solution:

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


class Solution:

	def Search(self, n, nums, target):
		if nums == None or len(nums) == 0:
			return 0
		low = 0
		high = len(nums) - 1
		while low <= high and nums[low] == nums[high]:
			if nums[low] == target:
				return 1
			low += 1
			high -= 1
		while low <= high:
			mid = low + high >> 1
			if nums[mid] == target:
				return 1
			if nums[mid] >= nums[low]:
				if target >= nums[low] and target < nums[mid]:
					high = mid - 1
				else:
					low = mid + 1
			elif target <= nums[high] and target > nums[mid]:
				low = mid + 1
			else:
				high = mid - 1
		return 0


class Solution:

	def Search(self, n, arr, k):
		ans = 0
		for i in range(n):
			if arr[i] == k:
				ans = 1
			else:
				continue
		return ans


class Solution:

	def Search(self, n, arr, k):
		(left, right) = (0, len(arr) - 1)
		while left <= right:
			mid = (left + right) // 2
			if arr[mid] == k:
				return 1
			if arr[mid] == arr[left] and mid != left:
				left += 1
				right -= 1
			if arr[left] <= arr[mid]:
				if arr[mid] < k or arr[left] > k:
					left = mid + 1
				else:
					right = mid - 1
			elif arr[right] < k or arr[mid] > k:
				right = mid - 1
			else:
				left = mid + 1
		return 0


class Solution:

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


class Solution:

	def Search(self, n, A, key):
		for num in A:
			if num == key:
				return 1
		return 0


class Solution:

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


class Solution:

	def Search(self, n, a, x):
		low = 0
		high = n - 1
		while low <= high:
			mid = low + (high - low) // 2
			if a[mid] == x:
				return 1
			elif a[low] == a[mid]:
				low += 1
				mid += 1
			elif a[low] < a[mid]:
				if a[low] <= x and a[mid] >= x:
					high = mid - 1
				else:
					low = mid + 1
			elif x >= a[mid] and x <= a[high]:
				low = mid + 1
			else:
				high = mid - 1
		return 0


class Solution:

	def Search(self, n, arr, k):
		x = 0
		for i in range(n):
			if arr[i] == k:
				x = 1
				break
		return x


class Solution:

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


class Solution:

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


class Solution:

	def Search(self, n, arr, k):
		low = 0
		high = n - 1
		while low <= high:
			mid = (low + high) // 2
			if arr[mid] == k:
				return 1
			if arr[low] == arr[mid] == arr[high]:
				for i in range(low, high + 1):
					if arr[i] == k:
						return 1
			if arr[low] <= arr[mid]:
				if k >= arr[low] and k <= arr[mid]:
					high = mid - 1
				else:
					low = mid + 1
			elif k >= arr[mid] and k <= arr[high]:
				low = mid + 1
			else:
				high = mid - 1
		return 0


class Solution:

	def Search(self, n, arr, k):
		try:
			ans = arr.index(k)
			if ans >= 0:
				return 1
		except:
			return 0