Given a sorted array arr[] of size N and an integer K. The task is to check if K is present in the array or not using ternary search.
Ternary Search- It is a divide and conquer algorithm that can be used to find an element in an array. In this algorithm, we divide the given array into three parts and determine which has the key (searched element).
Example 1:
Input:
N = 5, K = 6
arr[] = {1,2,3,4,6}
Output: 1
Exlpanation: Since, 6 is present in 
the array at index 4 (0-based indexing),
output is 1.
Example 2:
Input:
N = 5, K = 2
arr[] = {1,3,4,5,6}
Output: -1
Exlpanation: Since, 2 is not present 
in the array, output is -1.
Your Task:
You don't need to read input or print anything. Complete the function ternarySearch() which takes the sorted array arr[], its size N and the element K as input parameters and returns 1 if K is present in the array, else it returns -1. 
Expected Time Complexity: O(Log_{3}N)
Expected Auxiliary Space: O(1)
Constraints:
1 < N < 10^{6}
1 < K < 10^{6}
1 < arr[i] < 10^{6}

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

Complete search

Starter code: #User function Template for python3

class Solution:
    ##Complete this function
    def ternarySearch(self,arr,N,K):
        #Your code here

Solutions:
class Solution:

	def ternarySearch(self, arr, N, K):
		flag = 0
		for i in range(N):
			if arr[i] == K:
				flag = 1
		if flag == 1:
			return 1
		else:
			return -1


class Solution:

	def ternarySearch(self, arr, N, K):
		left = 0
		right = N - 1
		while left <= right:
			mid1 = left + (right - left) // 3
			mid2 = right - (right - left) // 3
			if arr[mid1] == K:
				return 1
			if arr[mid2] == K:
				return 1
			if K < arr[mid1]:
				right = mid1 - 1
			elif K > arr[mid2]:
				left = mid2 + 1
			else:
				left = mid1 + 1
				right = mid2 - 1
		return -1


class Solution:

	def ternarySearch(self, arr, N, K):
		low = 0
		high = N - 1
		while low <= high:
			mid1 = low + (high - low) // 3
			mid2 = high - (high - low) // 3
			if arr[mid1] == K:
				return 1
			elif arr[mid2] == K:
				return 1
			elif K < arr[mid1]:
				high = mid2 - 1
			elif K > arr[mid2]:
				low = mid2 + 1
			else:
				low = mid1 + 1
				high = mid2 - 1
		return -1


class Solution:

	def ternarySearch(self, arr, N, K):
		return 1 if K in arr else -1


class Solution:

	def ternarySearch(self, arr, N, K):
		l = 0
		r = N - 1
		while r >= l:
			mid1 = l + (r - l) // 3
			mid2 = r - (r - l) // 3
			if K == arr[mid1]:
				return 1
			if K == arr[mid2]:
				return 1
			if K < arr[mid1]:
				r = mid1 - 1
			elif K > arr[mid2]:
				l = mid2 + 1
			else:
				l = mid1 + 1
				r = mid2 - 1
		return -1


class Solution:

	def ternarySearch(self, arr, N, K):
		l = 0
		h = N - 1
		while l <= h:
			mid = (l + h) // 2
			if arr[mid] == K:
				return 1
			elif arr[mid] > K:
				h = mid - 1
			else:
				l = mid + 1
		return -1


class Solution:

	def ternarySearch(self, arr, N, K):
		for i in range(N):
			if arr[i] == K:
				return 1
		return -1


class Solution:

	def ternarySearch(self, arr, N, K):
		low = 0
		high = N - 1
		while low <= high:
			mid = (low + high) // 2
			if arr[mid] == K:
				return 1
			elif K < arr[mid]:
				high = mid - 1
			else:
				low = mid + 1
		return -1


class Solution:

	def ternarySearch(self, ar, N, key):
		assert 0 < N <= 10 ** 6
		assert 0 < K <= 10 ** 6
		for i in ar:
			assert 0 < i <= 10 ** 6
		l = 0
		r = N - 1
		while r >= l:
			mid1 = l + (r - l) // 3
			mid2 = r - (r - l) // 3
			if key == ar[mid1]:
				return 1
			if key == ar[mid2]:
				return 1
			if key < ar[mid1]:
				r = mid1 - 1
			elif key > ar[mid2]:
				l = mid2 + 1
			else:
				l = mid1 + 1
				r = mid2 - 1
		return -1


class Solution:

	def ternarySearch(self, ar, N, key):
		l = 0
		r = N - 1
		while r >= l:
			mid1 = l + (r - l) // 3
			mid2 = r - (r - l) // 3
			if key == ar[mid1]:
				return 1
			if key == ar[mid2]:
				return 1
			if key < ar[mid1]:
				r = mid1 - 1
			elif key > ar[mid2]:
				l = mid2 + 1
			else:
				l = mid1 + 1
				r = mid2 - 1
		return -1


class Solution:

	def ternarySearch(self, arr, N, K):
		start = 0
		end = N - 1
		while start <= end:
			mid1 = start + (end - start) // 3
			mid2 = end - (end - start) // 3
			if arr[mid1] == K or arr[mid2] == K:
				return 1
			elif arr[mid2] < K:
				start = mid2 + 1
			elif arr[mid1] > K:
				end = mid1 - 1
			else:
				start = mid1 + 1
				end = mid2 - 1
		return -1


class Solution:

	def ternarySearch(self, arr, N, K):
		a = 0
		b = N - 1
		while a <= b:
			diff = (b - a) // 3
			i1 = a + diff
			i2 = a + diff
			if arr[i1] == K or arr[i2] == K:
				return 1
			if K < arr[i1]:
				b = i1 - 1
			elif K > arr[i2]:
				a = i2 + 1
			else:
				a = i1 + 1
				b = i2 - 1
		return -1


class Solution:

	def ternarySearch(self, arr, N, K):
		l = 0
		h = N - 1
		while l <= h:
			m1 = l + (h - l) // 3
			m2 = h - (h - l) // 3
			if arr[m1] == K or arr[m2] == K:
				return 1
			elif arr[m1] > K:
				h = m1 - 1
			elif arr[m1] < K and arr[m2] > K:
				l = m1 + 1
				h = m2 - 1
			elif arr[m2] < K:
				l = m2 + 1
		return -1


class Solution:

	def ternarySearch(self, arr, N, K):
		l = 0
		r = N - 1
		while l <= r:
			m1 = l + (r - l) // 3
			m2 = r - (r - l) // 3
			if arr[m1] == K or arr[m2] == K:
				return 1
			elif K < arr[m1]:
				r = m1 - 1
			elif K > arr[m2]:
				l = m2 + 1
			else:
				l = m1 + 1
				r = m2 - 1
		return -1


class Solution:

	def ternarySearch(self, arr, N, target):
		(lo, hi) = (0, N - 1)
		while lo <= hi:
			mid1 = lo + (hi - lo) // 2
			mid2 = hi - (hi - lo) // 2
			if arr[mid1] == target:
				return 1
			if arr[mid2] == target:
				return 1
			if arr[mid1] > target:
				hi = mid1 - 1
			elif arr[mid1] < target:
				lo = mid1 + 1
			if arr[mid2] > target:
				hi = mid2 - 1
			elif arr[mid2] < target:
				lo = mid2 + 1
		return -1


class Solution:

	def ternarySearch(self, arr, N, K):
		if N >= 1 and N <= 10000000.0 and (K >= 1) and (K <= 10000000.0):
			return self.ternarySearchRecursive(arr, N - 1, K, 0)
		else:
			return -1

	def ternarySearchRecursive(self, arr, N, K, l):
		if N >= l:
			mid1 = l + (N - l) // 3
			mid2 = N - (N - l) // 3
			if arr[mid1] >= 1 and arr[mid1] <= 10000000.0 and (arr[mid2] >= 1) and (arr[mid2] <= 10000000.0):
				if K == arr[mid1] or K == arr[mid2]:
					return 1
				elif K < arr[mid1]:
					N = mid1 - 1
				elif K > arr[mid2]:
					l = mid2 + 1
				else:
					l = mid1 + 1
					N = mid2 - 1
				return self.ternarySearchRecursive(arr, N, K, l)
		return -1


class Solution:

	def ternarySearch(self, arr, N, K):

		def opn(arr, lo, hi, ele):
			if lo <= hi:
				m = lo + (hi - lo) // 3
				k = hi - (hi - lo) // 3
				if arr[m] == ele or arr[k] == ele:
					return 1
				if ele < arr[m]:
					return opn(arr, lo, m - 1, ele)
				elif ele > arr[k]:
					return opn(arr, k + 1, hi, ele)
				else:
					return opn(arr, m + 1, k - 1, ele)
			else:
				return -1
		return opn(arr, 0, N - 1, K)


def ternarySearch2(l, r, key, ar):
	if r >= l:
		mid1 = l + (r - l) // 3
		mid2 = r - (r - l) // 3
		if ar[mid1] == key:
			return mid1
		if ar[mid2] == key:
			return mid2
		if key < ar[mid1]:
			return ternarySearch2(l, mid1 - 1, key, ar)
		elif key > ar[mid2]:
			return ternarySearch2(mid2 + 1, r, key, ar)
		else:
			return ternarySearch2(mid1 + 1, mid2 - 1, key, ar)
	return -1

class Solution:

	def ternarySearch(self, arr, N, K):
		if ternarySearch2(0, N - 1, K, arr) != -1:
			return 1
		return -1


class Solution:

	def ternarySearch(self, arr, N, k):
		start = 0
		end = N - 1
		while start <= end:
			m1 = start + (end - start) // 3
			m2 = end - (end - start) // 3
			if k == arr[m1] or k == arr[m2]:
				return 1
			elif k < arr[m1]:
				end = m1 - 1
			elif k > arr[m2]:
				start = m2 + 1
			else:
				start = m1 + 1
				end = m2 - 1
		return -1


def ter_search(a, l, h, k):
	if l <= h:
		mid1 = l + (h - l) // 3
		mid2 = h - (h - l) // 3
		if a[mid1] == k:
			return 1
		if a[mid2] == k:
			return 1
		if a[mid1] > k:
			return ter_search(a, l, mid1 - 1, k)
		elif k > a[mid2]:
			return ter_search(a, mid2 + 1, h, k)
		else:
			return ter_search(a, mid1 + 1, mid2 - 1, k)
	return -1

class Solution:

	def ternarySearch(self, a, n, k):
		return ter_search(a, 0, n - 1, k)


class Solution:

	def ternarySearch(self, arr, N, K):
		start = 0
		end = N - 1
		while start <= end:
			lowerMid = start + (end - start) // 3
			upperMid = end - (end - start) // 3
			if arr[lowerMid] == K or arr[upperMid] == K:
				return 1
			elif arr[lowerMid] > K:
				end = lowerMid - 1
			elif arr[lowerMid] < K and K < arr[upperMid]:
				start = lowerMid + 1
				end = upperMid - 1
			else:
				start = upperMid + 1
		return -1


class Solution:

	def ternarySearch(self, arr, N, K):
		first = 0
		last = N - 1
		while first <= last:
			mid = (first + last) // 2
			if K < arr[mid]:
				last = mid - 1
			elif K > arr[mid]:
				first = mid + 1
			else:
				return 1
		return -1


class Solution:

	def ternarySearch(self, arr, N, K):
		s = 0
		e = N - 1
		while s <= e:
			m = s + (e - s) // 3
			n = s + (e - s) * 2 // 3
			if arr[m] == K:
				return 1
			elif arr[n] == K:
				return 1
			elif K < arr[m]:
				e = m - 1
			elif K > arr[n]:
				s = n + 1
			else:
				s = m + 1
				e = n - 1
		return -1


class Solution:

	def ternarySearch(self, arr, N, K):

		def _ternary(arr, k, mid1, mid2, l, h):
			if l > h or l > mid1 or mid1 > mid2 or (mid2 > h):
				return -1
			if k == arr[mid1] or k == arr[mid2]:
				return 1
			if k < arr[mid1]:
				h = mid1 - 1
			elif k > arr[mid1] and k < arr[mid2]:
				l = mid1 + 1
				h = mid2 - 1
			elif k > arr[mid2]:
				l = mid2 + 1
			mid1 = l + (h - l) // 3
			mid2 = h - (h - l) // 3
			return _ternary(arr, k, mid1, mid2, l, h)
		mid1 = (N - 1) // 3
		mid2 = mid1 * 2
		return _ternary(arr, K, mid1, mid2, 0, N - 1)


class Solution:

	def ternarySearch(self, arr, N, K):
		try:
			d = arr.index(K)
			return 1
		except:
			return -1


class Solution:

	def ternarySearch(self, arr, N, K):
		low = 0
		high = N - 1
		while low <= high:
			mid1 = low + (high - low) // 3
			mid2 = high - (high - low) // 3
			if arr[mid1] == K or arr[mid2] == K:
				return 1
			if K < arr[mid1]:
				high = mid1 - 1
			elif K > arr[mid2]:
				low = mid2 + 1
			else:
				low = mid1 + 1
				high = mid2 - 1
		return -1
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		NK = input().strip().split()
		N = int(NK[0])
		K = int(NK[1])
		arr = [int(x) for x in input().strip().split()]
		ob = Solution()
		print(ob.ternarySearch(arr, N, K))


class Solution:

	def ternarySearch(self, arr, N, k):
		if k in arr:
			return 1
		else:
			return -1
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		NK = input().strip().split()
		N = int(NK[0])
		K = int(NK[1])
		arr = [int(x) for x in input().strip().split()]
		ob = Solution()
		print(ob.ternarySearch(arr, N, K))


class Solution:

	def ternarySearch(self, arr, N, K):
		return self.ternary(arr, K, 0, N - 1)

	def ternary(self, arr, K, l, r):
		if r >= l:
			mid1 = l + (r - l) // 3
			mid2 = r - (r - l) // 3
			if arr[mid1] == K:
				return 1
			if arr[mid2] == K:
				return 1
			if K < arr[mid1]:
				return self.ternary(arr, K, l, mid1 - 1)
			elif K > arr[mid2]:
				return self.ternary(arr, K, mid2 + 1, r)
			else:
				return self.ternary(arr, K, mid1 + 1, mid2 - 1)
		return -1
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		NK = input().strip().split()
		N = int(NK[0])
		K = int(NK[1])
		arr = [int(x) for x in input().strip().split()]
		ob = Solution()
		print(ob.ternarySearch(arr, N, K))


class Solution:

	def ternarySearch(self, arr, N, K):

		def f(l, h, K):
			if l > h:
				return -1
			m = (h + l) // 2
			if arr[m] == K:
				return m
			elif arr[m] < K:
				return f(m + 1, h, K)
			return f(l, m - 1, K)
		return -1 if f(0, N - 1, K) == -1 else 1


class Solution:

	def ternarySearch(self, arr, N, K):
		s = 0
		e = N - 1
		while s <= e:
			mid1 = s + (e - s) // 3
			mid2 = e - (e - s) // 3
			if K == arr[mid1]:
				return 1
			if K == arr[mid2]:
				return 1
			if K < arr[mid1]:
				e = mid1 - 1
			elif K > arr[mid2]:
				s = mid2 + 1
			elif K > arr[mid1] and K < arr[mid2]:
				s = mid1 + 1
				e = mid2 - 1
		return -1


class Solution:

	def ternarySearch(self, arr, N, K):
		h = N - 1
		l = 0
		while l <= h:
			m1 = l + (h - l) // 3
			m2 = h - (h - l) // 3
			if arr[m1] == K:
				break
			elif arr[m2] == K:
				break
			elif arr[m1] > K:
				h = m1 - 1
			elif arr[m2] < K:
				l = m2 + 1
			else:
				l = m1 + 1
				h = m2 - 1
		else:
			return -1
		return 1