Your friend loves magic and he has coined a new term - "Magical number". To perform his magic, he needs that Magic number. There are N number of people in the magic show, seated according to their ages in ascending order. A magical number is that seat no. where the person has the same age as that of the given seat number.
Help your friend in finding out that "Magical number".
Note: If there are multiple magical numbers in the array, return the any one valid value.
Example:
Input:
1
10
-10 -1 0 3 10 11 30 50 100 150
Output:
3
Input:
The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is N, size of an array.
The second line of each test case contains N input A[].
Output:
Print "Magical Number"
Print "-1" when the index value does not match with the value. 
Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 1000
-1000 ≤ A[i] ≤ 1000

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: #User function Template for python3



def binarySearch(arr,low,high):

    '''

    arr: given array

    low: low index initialize as zero

    high: high index initialize as len(arr)-1

    return: magical n.o or -1

    '''

Solutions:
def binarySearch(arr, low, high):
	ans = -1
	while low <= high:
		m = (low + high) // 2
		if m == arr[m]:
			ans = arr[m]
			high = m - 1
		elif arr[m] > m:
			high = m - 1
		else:
			low = m + 1
	return ans


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


def binarySearch(arr, low, high):
	low = 0
	high = len(arr) - 1
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		if mid == arr[mid]:
			ans = arr[mid]
			high = mid - 1
		elif arr[mid] < mid:
			low = mid + 1
		else:
			high = mid - 1
	return ans


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


def binarySearch(arr, low, high):
	start = low
	end = high
	while start <= end:
		mid = (start + end) // 2
		if arr[mid] == mid:
			return mid
		elif mid < arr[mid]:
			end = mid - 1
		else:
			start = end + 1
	return -1


def binarySearch(arr, low, high):
	low = 0
	high = len(arr) - 1
	while low <= high:
		middle = (low + high) // 2
		if arr[middle] == middle:
			return middle
		elif arr[middle] > middle:
			high = middle - 1
		else:
			low = middle + 1
	return -1


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


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


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


def binarySearch(num, l, h):
	while l <= h:
		mid = l + h >> 1
		if num[mid] == mid:
			return mid
		elif num[mid] > mid:
			h = mid - 1
		else:
			l = mid + 1
	return -1


def binarySearch(arr, low, high):
	while low <= high:
		mid = int((low + high) / 2)
		value = arr[mid]
		if value == mid:
			return value
		if mid < value:
			high = mid - 1
		if mid > value:
			low = mid + 1
	return -1


def binarySearch(arr, low, high):
	for i in range(high + 1):
		mid = int(low + (high - low) / 2)
		if arr[mid] == mid:
			return mid
		elif arr[mid] < mid:
			low = mid + 1
		elif arr[mid] > mid:
			high = mid - 1
	return -1


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


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


def binarySearch(arr, low, high):
	l = 0
	r = len(arr) - 1
	while l <= r:
		mid = (l + r) // 2
		if arr[mid] == mid:
			return mid
		elif arr[mid] > mid:
			r = mid - 1
		else:
			l = mid + 1
	return -1


from bisect import bisect_right

def binarySearch(arr, l, r):
	while l <= r:
		mid = (l + r) // 2
		if arr[mid] == mid:
			return mid
		elif arr[mid] < mid:
			l = mid + 1
		else:
			r = mid - 1
	return -1


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


def binarySearch(arr, low, high):
	low = 0
	high = len(arr) - 1
	while low <= high:
		mid = (low + high) // 2
		if arr[mid] == mid:
			return mid
		if arr[mid] > mid:
			high = mid - 1
		if arr[mid] < mid:
			low = mid + 1
	return -1


def binarySearch(arr, low, high):
	arrLength = len(arr) - 1
	while low <= high:
		mid = (low + high) // 2
		if arr[mid] == mid:
			return mid
		elif arr[mid] < mid:
			low = mid + 1
		else:
			high = mid - 1
	return -1