Given a sorted and rotated array A of N distinct elements which is rotated at some point, and given an element key. The task is to find the index of the given element key in the array A. The whole array A is given as the range to search.
Example 1:
Input:
N = 9
A[] = {5, 6, 7, 8, 9, 10, 1, 2, 3}
key = 10
l = 0 , h = 8
Output:
5
Explanation: 10 is found at index 5.
Example 2:
Input:
N = 4
A[] = {3, 5, 1, 2}
key = 6
l = 0 , h = 3
Output:
-1
Explanation: There is no element that has value 6.
Your Task:
Complete the function search() which takes an array arr[] and start, end index of the array and the K as input parameters, and returns the answer.
Can you solve it in expected time complexity?
Expected Time Complexity: O(log N).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 10^{7}
0 ≤ A[i] ≤ 10^{8}
1 ≤ key ≤ 10^{8}

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

Complete search

Starter code: #User function Template for python3



class Solution:

    def search(self, A : list, l : int, h : int, key : int):

        # l: The starting index

        # h: The ending index, you have to search the key in this range

        # Complete this function

Solutions:
class Solution:

	def search(self, A: list, l: int, h: int, key: int):
		if key in A:
			return A.index(key)
		else:
			return -1


class Solution:

	def search(self, A: list, l: int, h: int, key: int):
		for (i, n) in enumerate(A):
			if n == key:
				return i
		return -1


class Solution:

	def search(self, A: list, l: int, h: int, key: int):
		for i in range(len(A)):
			if A[i] == key:
				return i
		return -1


class Solution:

	def search(self, a: list, l: int, h: int, k: int):
		for i in range(n):
			if a[i] == k:
				return i
		return -1


class Solution:

	def search(self, A: list, l: int, h: int, key: int):
		try:
			ind = A.index(key)
			return ind
		except:
			return -1


from bisect import bisect_left

class Solution:

	def search(self, a: list, l: int, h: int, key: int):
		if len(a) == 1:
			if a[0] == key:
				return 0
			return -1
		if a[-1] < a[-2]:
			pivot = h
		elif a[0] > a[1]:
			pivot = 1
		else:
			while l <= h:
				mid = l + (h - l) // 2
				if mid == len(a) - 1:
					pivot = len(a)
					break
				if a[mid - 1] < a[mid] > a[mid + 1]:
					pivot = mid + 1
					break
				elif a[mid - 1] > a[mid]:
					pivot = mid
					break
				elif a[0] > a[mid]:
					h = mid - 1
				else:
					l = mid + 1
		(p, q) = (bisect_left(a, key, 0, pivot), bisect_left(a, key, pivot, len(a)))
		if p < len(a) and a[p] == key:
			return p
		if q < len(a) and a[q] == key:
			return q
		return -1


class Solution:

	def bs(self, l, f, r, t):
		while f <= r:
			mid = (f + r) // 2
			if l[mid] == t:
				return mid
			if l[mid] > t:
				r = mid - 1
			else:
				f = mid + 1
		return -1

	def search(self, A: list, l: int, h: int, key: int):
		if A[0] < A[-1]:
			return self.bs(A, 0, h, key)
		(f, r) = (l, h)
		while f <= r:
			mid = (f + r) // 2
			if A[mid] >= A[0]:
				f = mid + 1
			else:
				r = mid - 1
		if A[0] <= key:
			return self.bs(A, 0, r, key)
		return self.bs(A, f, h, key)


class Solution:

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


class Solution:

	def search(self, A: list, l: int, h: int, key: int):
		a = []
		for i in A:
			if i == key:
				a.append(A.index(i))
		if a == []:
			return -1
		else:
			return a[0]


class Solution:

	def search(self, A: list, low: int, high: int, key: int):
		while low <= high:
			mid = (high + low) // 2
			if A[mid] == key:
				return mid
			if A[mid] >= A[low]:
				if key >= A[low] and key <= A[mid]:
					high = mid - 1
				else:
					low = mid + 1
			elif key >= A[mid] and key <= A[high]:
				low = mid + 1
			else:
				high = mid - 1
		return -1


class Solution:

	def search(self, A: list, l: int, h: int, key: int):
		start = 0
		end = len(A) - 1
		while start <= end:
			mid = (start + end) // 2
			if A[mid] == key:
				return mid
			if A[start] <= A[mid]:
				if A[start] <= key < A[mid]:
					end = mid - 1
				else:
					start = mid + 1
			elif A[mid] < key <= A[end]:
				start = mid + 1
			else:
				end = mid - 1
		return -1


class Solution:

	def search(self, nums: list, l: int, h: int, target: int):
		if nums[0] is target:
			return 0
		start = 0
		end = len(nums) - 1
		while start <= end:
			mid = (start + end) // 2
			if nums[start] == target:
				return start
			if nums[mid] == target:
				return mid
			if nums[end] == target:
				return end
			if nums[mid] == target:
				return mid
			if nums[start] < nums[mid]:
				if target >= nums[start] and target < nums[mid]:
					end = mid - 1
				else:
					start = mid + 1
			elif nums[mid] < nums[end] and (target > nums[end] or target < nums[mid]):
				end = mid - 1
			else:
				start = mid + 1
		return -1


class Solution:

	def search(self, A: list, l: int, h: int, key: int):
		a = A
		low = l
		high = h
		target = key
		while low <= high:
			mid = (low + high) // 2
			if a[mid] == target:
				return mid
			if a[low] <= a[mid]:
				if target >= a[low] and target <= a[mid]:
					high = mid - 1
				else:
					low = mid + 1
			elif target >= a[mid] and target <= a[high]:
				low = mid + 1
			else:
				high = mid - 1
		return -1


class Solution:

	def search(self, nums: list, lo: int, hi: int, target: int):

		def search(nums, lo, hi):
			mid = (lo + hi) // 2
			if nums[mid] == target:
				return mid
			if lo == hi:
				return -1
			if nums[lo] < nums[mid]:
				if target >= nums[lo] and target < nums[mid]:
					return search(nums, lo, mid - 1)
				else:
					return search(nums, mid + 1, hi)
			elif hi - mid == 1:
				if nums[hi] == target:
					return hi
				else:
					return search(nums, lo, mid)
			elif nums[mid + 1] < nums[hi]:
				if target >= nums[mid + 1] and target <= nums[hi]:
					return search(nums, mid + 1, hi)
				else:
					return search(nums, lo, mid - 1)
			return -1
		return -1 if not nums else search(nums, 0, len(nums) - 1)


class Solution:

	def search(self, arr: list, l: int, h: int, key: int):
		while l <= h:
			mid = (l + h) // 2
			if arr[mid] == key:
				return mid
			if arr[l] <= arr[mid]:
				if key > arr[mid] or key < arr[l]:
					l = mid + 1
				else:
					h = mid - 1
			elif key < arr[mid] or key > arr[h]:
				h = mid - 1
			else:
				l = mid + 1
		return -1


class Solution:

	def search(self, a: list, l: int, r: int, key: int):
		while l <= r:
			mid = (l + r) // 2
			if a[mid] == key:
				return mid
			elif a[l] <= a[mid]:
				if key < a[l] or key > a[mid]:
					l = mid + 1
				else:
					r = mid - 1
			elif key > a[r] or key < a[mid]:
				r = mid - 1
			else:
				l = mid + 1
		return -1


class Solution:

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


class Solution:

	def search(self, nums: list, l: int, h: int, key: int):
		if not nums:
			return -1
		(l, r) = (0, len(nums) - 1)
		while l < r:
			mid = (l + r) // 2
			if nums[mid] == key:
				return mid
			elif nums[mid] > nums[l]:
				if nums[l] <= key <= nums[mid]:
					r = mid
				else:
					l = mid + 1
			elif nums[mid + 1] <= key <= nums[r]:
				l = mid + 1
			else:
				r = mid
		return l if nums[l] == key else -1


class Solution(object):

	def search(self, nums: list, left: int, right: int, target: int):
		while left <= right:
			mid = (left + right) // 2
			curr = nums[mid]
			if curr == target:
				return mid
			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 -1


class Solution:

	def search(self, A: list, l: int, h: int, key: int):

		def findPivot(arr, low, high):
			if high < low:
				return -1
			if high == low:
				return low
			mid = int((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]:
				return findPivot(arr, low, mid - 1)
			return findPivot(arr, mid + 1, high)

		def binarySearch(arr, low, high, key):
			if high < low:
				return -1
			mid = int((low + high) / 2)
			if key == arr[mid]:
				return mid
			if key > arr[mid]:
				return binarySearch(arr, mid + 1, high, key)
			return binarySearch(arr, low, mid - 1, key)
		pivot = findPivot(A, l, h)
		if pivot == -1:
			return binarySearch(A, 0, n - 1, key)
		if key == A[pivot]:
			return pivot
		if A[0] <= key:
			return binarySearch(A, 0, pivot - 1, key)
		return binarySearch(A, pivot + 1, len(A) - 1, key)


class Solution:

	def search(self, A: list, l: int, h: int, key: int):
		if h == l:
			if A[l] == key:
				return l
			else:
				return -1
		mid = l + (h - l) // 2
		l_result = self.search(A, l, mid, key)
		if l_result != -1:
			return l_result
		r_result = self.search(A, mid + 1, h, key)
		if r_result != -1:
			return r_result
		return -1


class Solution:

	def search(self, A: list, l: int, h: int, key: int):
		index = -1
		i = 0
		while i < h:
			if A[i] == key:
				index = i
				break
			if A[h] == key:
				index = h
				break
			i += 1
			h -= 1
		return index


class Solution:

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


class Solution:

	def search(self, a: list, l: int, h: int, key: int):
		if key in a:
			return a.index(key)
		return -1


class Solution:

	def search(self, A: list, l: int, h: int, key: int):
		m = 0
		flag = 0
		for i in range(l, h + 1):
			if A[i] == key:
				flag = 1
				m = i
				break
		if flag == 1:
			return m
		else:
			return -1