Given a sorted array of size N and an integer K, find the position(0-based indexing) at which K is present in the array using binary search.
Example 1:
Input:
N = 5
arr[] = {1 2 3 4 5} 
K = 4
Output: 3
Explanation: 4 appears at index 3.
Example 2:
Input:
N = 5
arr[] = {11 22 33 44 55} 
K = 445
Output: -1
Explanation: 445 is not present.
Your Task:  
You dont need to read input or print anything. Complete the function binarysearch() which takes arr[], N and K as input parameters and returns the index of K in the array. If K is not present in the array, return -1.
Expected Time Complexity: O(LogN)
Expected Auxiliary Space: O(LogN) if solving recursively and O(1) otherwise.
Constraints:
1 <= N <= 10^{5}
1 <= arr[i] <= 10^{6}
1 <= K <= 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Complete search

Data structures

Divide and conquer

Starter code: #User function template for Python



class Solution:	

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

		# code here

Solutions:
class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def binarysearch(self, arr, n, k):
		l = 0
		r = n - 1
		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


class Solution:

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


class Solution:

	def binarysearch(self, arr, n, k):
		s = 0
		for i in range(n):
			if k == arr[i]:
				s = i
		if s == 0:
			return -1
		else:
			return s


class Solution:

	def binarysearch(self, arr, n, k):
		present = True
		result = -1
		for i in range(n):
			if arr[i] != k:
				i += 1
			else:
				result = i
		return result


class Solution:

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


class Solution:

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


class Solution:

	def binarysearch(self, arr, n, k):
		i = 0
		bal = False
		for a in arr:
			if a == k:
				bal = True
				break
			else:
				i += 1
		return i if bal else -1


class Solution:

	def bina(self, arr, start, low, k):
		if low > start:
			mid = (start + low) // 2
			if arr[mid] == k:
				return mid
			elif arr[mid] > k:
				return self.bina(arr, start, mid, k)
			elif arr[mid] < k:
				return self.bina(arr, mid + 1, low, k)
		else:
			return -1

	def binarysearch(self, arr, n, k):
		return self.bina(arr, 0, n, k)


class Solution:

	def binarysearch(self, arr, n, key):
		lower = 0
		upper = len(arr) - 1
		while lower <= upper:
			mid = (upper + lower) // 2
			if arr[mid] < key:
				lower = lower + 1
			elif arr[mid] > key:
				upper = upper - 1
			elif arr[mid] == key:
				return mid
				break
		else:
			return -1


class Solution:

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


import math

class Solution:

	def binarySearchRec(self, arr, low, high, k):
		if low == high and arr[low] == k:
			return low
		elif low == high:
			return -1
		else:
			mid = (low + high) // 2
			if arr[mid] == k:
				return mid
			if arr[mid] > k:
				return self.binarySearchRec(arr, low, mid, k)
			else:
				return self.binarySearchRec(arr, mid + 1, high, k)

	def binarysearch(self, arr, n, k):
		return self.binarySearchRec(arr, 0, n - 1, k)


class Solution:

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


class Solution:

	def binarysearch(self, arr, n, k):
		(Start, End) = (0, n - 1)
		while Start <= End:
			Mid = (Start + End) // 2
			if arr[Mid] == k:
				return Mid
			elif arr[Mid] < k:
				Start = Mid + 1
			else:
				End = Mid - 1
		return -1


class Solution:

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


class Solution:

	def bin_search(self, arr, left, right, key):
		if left > right:
			return -1
		mid = (left + right) // 2
		if arr[mid] == key:
			return mid
		elif arr[mid] > key:
			return self.bin_search(arr, left, mid - 1, key)
		else:
			return self.bin_search(arr, mid + 1, right, key)

	def binarysearch(self, arr, n, k):
		left = 0
		right = n - 1
		location_of_key = self.bin_search(arr, left, right, k)
		return location_of_key


class Solution:

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


class Solution:

	def binarysearch(self, arr, n, k):
		arr.sort()
		left = 0
		right = n - 1
		found = False
		while left <= right:
			mid = (left + right) // 2
			if arr[mid] == k:
				found = True
				break
			elif arr[mid] < k:
				left += 1
			else:
				right -= 1
		return mid if found else -1


class Solution:

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

		def binary_return(nums, lb, ub, item):
			if lb <= ub:
				mid = int((lb + ub) / 2)
				if item == nums[mid]:
					return mid
				elif nums[mid] > k:
					return binary_return(nums, lb, mid - 1, item)
				else:
					return binary_return(nums, mid + 1, ub, item)
			else:
				return -1
		return binary_return(arr, 0, n - 1, k)


class Solution:

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


class Solution:

	def binarysearch(self, arr, n, k):
		if k in arr:
			for i in range(n):
				if arr[i] == k:
					return i
					break
				else:
					continue
		else:
			return -1


class Solution:

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


class Solution:

	def binarysearch(self, arr, n, k):
		t = 0
		r = 0
		for i in arr:
			if k == i:
				t = arr.index(i)
				r = r + 1
		if r > 0:
			return t
		else:
			return -1


class Solution:

	def binarysearch(self, arr, n, k):
		x = 0
		for i in arr:
			if i == k:
				return x
			x += 1
		return -1


class Solution:

	def binarysearch(self, arr, n, k):
		S = 0
		E = n - 1
		while S <= E:
			M = (S + E) // 2
			if arr[M] == k:
				return M
			elif arr[M] > k:
				E = M - 1
			else:
				S = M + 1
		return -1


class Solution:

	def binarysearch(self, arr, n, k):
		found = False
		last = False
		startIndex = 0
		while not found:
			medianIndex = int(len(arr) // 2)
			if arr[medianIndex] == k:
				return medianIndex + startIndex
			elif arr[medianIndex] > k:
				arr = arr[:medianIndex]
			else:
				startIndex += medianIndex
				arr = arr[medianIndex:]
			if last:
				return -1
			if len(arr) == 1:
				last = True