Given a sorted and rotated array A of N distinct elements which are rotated at some point, and given an element K. The task is to find the index of the given element K in array A.
Example 1:
Input:
N = 9
A[] = {5,6,7,8,9,10,1,2,3}
K = 10
Output: 5
Explanation: 10 is found at index 5.
Example 1:
Input:
N = 3
A[] = {3,1,2}
K = 1
Output: 1
User Task:
Complete Search() function and return the index of the element K if found in the array. If the element is not present, then return -1.
Expected Time Complexity: O(log N).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 10^{7}
0 ≤ A_{i} ≤ 10^{8}
1 ≤ K ≤ 10^{8}

Source: geeksforgeeks | Difficulty: EASY
Tags: Divide and conquer

Complete search

Starter code: #User function Template for python3



def Search(arr,n,k):

    #code here

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


def search(arr, left, right, item):
	if left > right:
		return -1
	mid = (left + right) // 2
	if arr[mid] == item:
		return mid
	if arr[left] < arr[mid]:
		if item >= arr[left] and item < arr[mid]:
			return search(arr, left, mid - 1, item)
		else:
			return search(arr, mid + 1, right, item)
	elif arr[right] > arr[mid]:
		if item > arr[mid] and item <= arr[right]:
			return search(arr, mid + 1, right, item)
		else:
			return search(arr, left, mid - 1, item)
	elif arr[mid] == arr[left]:
		return search(arr, mid + 1, right, item)
	else:
		result = search(arr, left, mid - 1, item)
		if result == -1:
			result = search(arr, mid + 1, right, item)
		else:
			return result

def Search(arr, n, k):
	return search(arr, 0, n - 1, k)


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


def binarysearch(arr, k, l, h):
	if l > h:
		return -1
	m = (l + h) // 2
	if k == arr[m]:
		return m
	elif arr[l] <= arr[m]:
		if k >= arr[l] and k <= arr[m]:
			return binarysearch(arr, k, l, m - 1)
		else:
			return binarysearch(arr, k, m + 1, h)
	elif k > arr[m] and k <= arr[h]:
		return binarysearch(arr, k, m + 1, h)
	else:
		return binarysearch(arr, k, l, m - 1)

def Search(arr, n, k):
	l = 0
	h = n - 1
	result = binarysearch(arr, k, l, h)
	return result


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


def Search(arr, n, k):
	if k not in arr:
		return -1
	else:
		for i in range(n // 2):
			if arr[i] == k:
				return i
			elif arr[n - 1 - i] == k:
				return n - 1 - i


def Search(arr, n, k):
	try:
		return arr.index(k)
	except:
		return -1


def Search(arr, n, k):
	left = 0
	right = n - 1
	if k not in arr:
		return -1
	while left < right:
		if arr[left] == k:
			return left
		if arr[right] == k:
			return right
		left += 1
		right -= 1


def Search(arr, n, k):
	if k in arr:
		return arr.index(k)
	return -1


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


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


def Search(arr, n, k):
	start = 0
	end = n - 1
	ans = -1
	while start <= end:
		mid = start + (end - start) // 2
		if arr[mid] == k:
			return mid
		elif arr[start] <= arr[mid]:
			if arr[mid] > k and arr[start] <= k:
				end = mid - 1
			else:
				start = mid + 1
		elif k > arr[mid] and k <= arr[end]:
			start = mid + 1
		else:
			end = mid - 1
	return ans


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


def Search(arr, n, k):
	(low, high) = (0, n - 1)
	while low <= high:
		mid = (low + high) // 2
		if arr[mid] == k:
			return mid
		if 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 -1


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


def Search(arr, n, k):
	pivot = -1
	for i in range(n - 1):
		if arr[i] > arr[i + 1]:
			pivot = i + 1
	l = 0
	h = pivot - 1
	m = (l + h) // 2
	arr1 = arr[pivot:]
	arr2 = arr[:pivot]
	while l <= h:
		m = (l + h) // 2
		if arr[m] == k:
			return m
		elif arr[m] > k:
			h = m - 1
		elif arr[m] < k:
			l = m + 1
	l = pivot
	h = n - 1
	m = (l + h) // 2
	while l <= h:
		m = (l + h) // 2
		if arr[m] == k:
			return m
		elif arr[m] > k:
			h = m - 1
		elif arr[m] < k:
			l = m + 1
	return -1


def Search(arr, n, k):
	am = arr.index(max(arr))
	low = 0
	high = len(arr) - 1
	if k == arr[am]:
		return am
	elif k <= arr[len(arr) - 1]:
		low = am + 1
	else:
		high = am - 1
	mid = (low + high) // 2
	while low <= high:
		mid = (low + high) // 2
		if arr[mid] == k:
			return mid
		elif k > arr[mid]:
			low = mid + 1
		else:
			high = mid - 1
	return -1


def Search(arr, n, k):
	start = 0
	end = n - 1
	while start < n and end >= 0:
		if arr[start] == k:
			return start
		if arr[end] == k:
			return end
		start += 1
		end -= 1
	return -1


def Search(arr, n, k):
	a = 0
	b = n - 1
	while a <= b:
		if arr[a] == k:
			return a
		elif arr[b] == k:
			return b
		a += 1
		b -= 1
	return -1


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


def Search(arr, n, k):
	(low, high) = (0, n - 1)
	while low <= high:
		mid = (low + high) // 2
		if arr[mid] >= arr[0]:
			low = mid + 1
		else:
			high = mid - 1
	rotations = low
	(low, high) = (0, n - 1)
	while low <= high:
		mid = (low + high) // 2
		rmid = (mid + rotations) % n
		if arr[rmid] <= k:
			low = mid + 1
		else:
			high = mid - 1
	idx = low - 1
	ridx = (idx + rotations) % n
	if arr[ridx] == k:
		return ridx
	return -1


def Search(arr, n, k):
	for i in range(n - 1):
		if arr[i] > arr[i + 1]:
			pivot = i
			break
	if arr[i] >= k and arr[0] <= k:
		l = 0
		u = i
	else:
		l = i + 1
		u = n - 1
	while l <= u:
		m = (l + u) // 2
		if arr[m] == k:
			return m
		elif arr[m] > k:
			u = m - 1
		else:
			l = m + 1
	return -1


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

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

def Search(arr, n, key):
	pivot = findPivot(arr, 0, n - 1)
	if pivot == -1:
		return binSearch(arr, 0, n - 1, key)
	if arr[pivot] == key:
		return pivot
	if arr[0] <= key:
		return binSearch(arr, 0, pivot - 1, key)
	return binSearch(arr, pivot + 1, n - 1, key)


def Search(arr, n, k):
	arr = arr + [k]
	b = arr.index(k)
	if b == n:
		return -1
	return b


def Search(arr, n, k):
	if k not in arr:
		return -1
	list_arr = arr[0:1] + arr[1:]
	list_arr.sort()
	low = 0
	high = n - 1
	while low <= high:
		mid = (low + high) // 2
		if list_arr[mid] == k:
			break
		elif list_arr[mid] < k:
			low = mid + 1
		else:
			high = mid - 1
	if list_arr[mid] == k:
		return arr.index(k)


def search(arr, l, h, k):
	if l > h:
		return -1
	mid = (l + h) // 2
	if arr[mid] == k:
		return mid
	if arr[l] <= arr[mid]:
		if k >= arr[l] and k <= arr[mid]:
			return search(arr, l, mid - 1, k)
		return search(arr, mid + 1, h, k)
	if k >= arr[mid] and k <= arr[h]:
		return search(arr, mid + 1, h, k)
	return search(arr, l, mid - 1, k)

def Search(arr, n, k):
	low = 0
	high = n - 1
	return search(arr, low, high, k)


def Search(arr, n, k):
	i = 0
	while i < n:
		if k in arr:
			return arr.index(k)
		i += 1
	return -1


def Search(arr, n, k):
	if not arr:
		return -1
	(l, r) = (0, len(arr) - 1)
	while l <= r:
		mid = (l + r) // 2
		if arr[mid] == k:
			return mid
		if arr[l] <= arr[mid]:
			if arr[l] <= k <= arr[mid]:
				r = mid - 1
			else:
				l = mid + 1
		elif arr[mid] <= k <= arr[r]:
			l = mid + 1
		else:
			r = mid - 1
	return -1


def Search(arr, n, k):
	for i in arr:
		if i == k:
			return arr.index(i)
	return -1


def fun(nums):
	(l, h) = (0, len(nums) - 1)
	while True:
		mid = (l + h) // 2
		if len(nums) > 2:
			if nums[0] < nums[len(nums) - 1]:
				return 0
			elif nums[mid] >= nums[l] and nums[mid] >= nums[h]:
				if l == h - 1:
					if nums[mid + 1] >= nums[mid] and nums[mid - 1] <= nums[mid]:
						return mid
					return mid + 1
				else:
					l = mid
			elif nums[mid] <= nums[l] and nums[mid] <= nums[h]:
				if h == l + 1:
					if nums[mid + 1] >= nums[mid] and nums[mid - 1] <= nums[mid]:
						return mid
					return mid + 1
				else:
					h = mid
			else:
				return -1
		elif len(nums) == 2:
			if nums[0] < nums[1]:
				return 0
			else:
				return 1
		else:
			return 0

def binary(arr, x):
	(l, h) = (0, len(arr) - 1)
	n = len(arr)
	while l <= h:
		mid = l + (h - l) // 2
		if mid < n and arr[mid] == x:
			return mid
		elif mid < n and arr[mid] > x:
			h = mid - 1
		else:
			l = mid + 1
	return -1

def Search(arr, n, k):
	t = fun(arr)
	p1 = binary(arr[:t], k)
	p2 = binary(arr[t:], k)
	if p1 != -1:
		return p1
	if p2 != -1:
		return t + p2
	return -1


def search(A, l, h, key):
	if h >= l:
		mid = int(l + (h - l) / 2)
		if A[mid] == key:
			return mid
		if A[l] <= A[mid]:
			if key >= A[l] and key <= A[mid]:
				return search(A, l, mid - 1, key)
			else:
				return search(A, mid + 1, h, key)
		if key >= A[mid] and key <= A[h]:
			return search(A, mid + 1, h, key)
		return search(A, l, mid - 1, key)
	else:
		return -1

def Search(arr, n, k):
	return search(arr, 0, n - 1, k)


def Search(arr, n, k):
	pivot = 0
	for i in range(len(arr) - 1):
		if arr[i] > arr[i + 1]:
			pivot = i
	if arr[pivot] == k:
		return pivot
	left = 0
	right = pivot - 1
	while left <= right:
		mid = (left + right) // 2
		if arr[mid] == k:
			return mid
		elif arr[mid] > k:
			right = mid - 1
		elif arr[mid] < k:
			left = mid + 1
	left = pivot + 1
	right = len(arr) - 1
	while left <= right:
		mid = (left + right) // 2
		if arr[mid] == k:
			return mid
		elif arr[mid] > k:
			right = mid - 1
		elif arr[mid] < k:
			left = mid + 1
	return -1


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


def Search(arr, n, k):
	i = 0
	while True:
		if arr[i] == k:
			break
		i = i + 1
		if i > n - 1:
			break
	if i <= n - 1:
		return i
	else:
		return -1


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


def Search(arr, n, k):
	if k not in arr:
		return -1
	else:
		return arr.index(k)


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

def bis(arr, s, e, k):
	start = s
	end = e
	while start <= end:
		mid = start + (end - start) // 2
		if arr[mid] == k:
			return mid
		elif arr[mid] > k:
			end = mid - 1
		else:
			start = mid + 1
	return -1

def Search(arr, n, k):
	pivot = getpivot(arr, n)
	if arr[pivot] <= k and k <= arr[n - 1]:
		return bis(arr, pivot, n - 1, k)
	else:
		return bis(arr, 0, pivot - 1, k)


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

def bis(arr, l, r, x):
	if r >= l:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] > x:
			return bis(arr, l, mid - 1, x)
		else:
			return bis(arr, mid + 1, r, x)
	else:
		return -1

def Search(arr, n, k):
	pivot = getpivot(arr, n)
	if arr[pivot] <= k and k <= arr[n - 1]:
		return bis(arr, pivot, n - 1, k)
	else:
		return bis(arr, 0, pivot - 1, k)


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

def bs(arr, l, r, x):
	if r >= l:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] > x:
			return bs(arr, l, mid - 1, x)
		else:
			return bs(arr, mid + 1, r, x)
	else:
		return -1

def Search(arr, n, k):
	pivot = gpivot(arr, n)
	if arr[pivot] <= k and k <= arr[n - 1]:
		return bs(arr, pivot, n - 1, k)
	else:
		return bs(arr, 0, pivot - 1, k)


def pSearch(arr, low, high):
	if high < low:
		return -1
	if high == low:
		return low
	mid = (low + high) // 2
	if low == mid and arr[mid + 1] < arr[mid] or (high == mid and arr[mid - 1] < arr[mid]):
		return mid
	if arr[mid - 1] < arr[mid] and arr[mid + 1] < arr[mid]:
		return mid
	if arr[low] > arr[mid]:
		return pSearch(arr, low, mid - 1)
	return pSearch(arr, mid + 1, high)

def bSearch(arr, low, high, k):
	if high < low:
		return -1
	mid = (low + high) // 2
	if arr[mid] == k:
		return mid
	if arr[mid] > k:
		return bSearch(arr, low, mid - 1, k)
	return bSearch(arr, mid + 1, high, k)

def Search(arr, n, k):
	pivot = pSearch(arr, 0, n - 1)
	if pivot == -1:
		return bSearch(arr, 0, n - 1, k)
	if arr[pivot] == k:
		return pivot
	if arr[0] > k:
		return bSearch(arr, pivot + 1, n - 1, k)
	return bSearch(arr, 0, pivot - 1, k)


def B_S(arr, s, e, k):
	mid = s + (e - s) // 2
	while s <= e:
		if arr[mid] == k:
			return mid
		elif arr[mid] < k:
			s = mid + 1
		else:
			e = mid - 1
		mid = s + (e - s) // 2
	return -1

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

def Search(arr, n, k):
	min_ind = findMin(arr, n)
	ls = B_S(arr, 0, min_ind - 1, k)
	rs = B_S(arr, min_ind, n - 1, k)
	if ls == -1:
		return rs
	if rs == -1:
		return ls


def binarysearch(arr, n, s, e, k):
	mid = s + (e - s) // 2
	while s <= e:
		if arr[mid] == k:
			return mid
		elif k < arr[mid]:
			e = mid - 1
		else:
			s = mid + 1
		mid = s + (e - s) // 2
	return -1

def findMin(arr, n):
	(low, high) = (0, n - 1)
	while low <= high:
		if arr[low] <= arr[high]:
			return low
		mid = low + (high - low) // 2
		Next = (mid + 1) % n
		Prev = (mid + n - 1) % n
		if arr[mid] <= arr[Next] and arr[mid] <= arr[Prev]:
			return mid
		elif arr[mid] <= arr[high]:
			high = mid - 1
		elif arr[mid] >= arr[low]:
			low = mid + 1

def Search(arr, n, k):
	index = findMin(arr, n)
	leftSearch = binarysearch(arr, n, 0, index - 1, k)
	rightSearch = binarysearch(arr, n, index, n - 1, k)
	if leftSearch == -1:
		return rightSearch
	if rightSearch == -1:
		return leftSearch


def Search(arr, n, k):
	l = 0
	r = n - 1
	min_idx = -1
	while l <= r:
		mid = (l + r) // 2
		if arr[mid] <= arr[-1]:
			min_idx = mid
			r = mid - 1
		else:
			l = mid + 1
	max_idx = max(0, min_idx - 1)

	def bs(l, r):
		while l <= r:
			mid = (l + r) // 2
			if arr[mid] == k:
				return mid
			elif arr[mid] < k:
				l = mid + 1
			else:
				r = mid - 1
		return -1
	if arr[0] <= k <= arr[max_idx]:
		return bs(0, max_idx)
	else:
		return bs(min_idx, n - 1)


def Search(arr, n, k):
	(s, e) = (0, n - 1)
	while s <= e:
		m = s + (e - s) // 2
		if arr[m] == k:
			return m
		if arr[s] <= arr[m]:
			if k >= arr[s] and k < arr[m]:
				e = m - 1
			else:
				s = m + 1
		elif k > arr[m] and k <= arr[e]:
			s = m + 1
		else:
			e = m - 1
	return -1