Given a sorted array Arr[](0-index based) consisting of N distinct integers and an integer k, the task is to find the index of k, if its present in the array Arr[]. Otherwise, find the index where k must be inserted to keep the array sorted.
Example 1:
Input:
N = 4
Arr = {1, 3, 5, 6}
k = 5
Output: 2
Explaination: Since 5 is found at index 2 
as Arr[2] = 5, the output is 2.
Example 2:
Input:
N = 4
Arr = {1, 3, 5, 6}
k = 2
Output: 1
Explaination: Since 2 is not present in 
the array but can be inserted at index 1 
to make the array sorted.
Your Task:
You don't need to read input or print anything. Your task is to complete the function searchInsertK() which takes the array Arr[] and its size N and k as input parameters and returns the index.
Expected Time Complexity: O(logN)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{4}
-10^{3} ≤ Arr[i] ≤ 10^{3}
-10^{3} ≤ k ≤ 10^{3}

Difficulty: EASY
Tags: Complete search
Skill types: Complete search
Expected Time Complexity: O(logN)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def searchInsertK(self, Arr, N, k):

        # code here

Solutions:
from bisect import bisect_left

class Solution:

	def searchInsertK(self, Arr, N, k):
		return bisect_left(Arr, k)


class Solution:

	def searchInsertK(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:
				if mid == N - 1 or Arr[mid + 1] > k:
					return mid + 1
				else:
					start = mid + 1
			elif mid == 0 or Arr[mid - 1] < k:
				return mid
			else:
				end = mid - 1


class Solution:

	def searchInsertK(self, Arr, N, k):
		(l, r) = (0, N - 1)
		while l <= r:
			m = (l + r) // 2
			if Arr[m] == k:
				return m
			elif Arr[m] < k:
				l = m + 1
			else:
				r = m - 1
		return l


import bisect

class Solution:

	def searchInsertK(self, Arr, N, k):
		if k in Arr:
			return Arr.index(k)
		return bisect.bisect(Arr, k)


class Solution:

	def searchInsertK(self, Arr, N, k):
		target = k
		if target in Arr:
			return Arr.index(target)
		else:
			for i in range(len(Arr)):
				if target < Arr[i]:
					return 0
				elif target > Arr[len(Arr) - 1]:
					return len(Arr)
				elif target > Arr[i] and target < Arr[i + 1]:
					return i + 1


class Solution:

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


class Solution:

	def searchInsertK(self, Arr, N, k):
		if k in Arr:
			return Arr.index(k)
		else:
			Arr.append(k)
			Arr = sorted(Arr)
			return Arr.index(k)


class Solution:

	def searchInsertK(self, Arr, N, k):
		low = 0
		high = N - 1
		while low <= high:
			mid = (low + high) // 2
			if Arr[mid] == k:
				return mid
			if k < Arr[mid]:
				high = mid - 1
			else:
				low = mid + 1
		return low


import bisect

class Solution:

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


class Solution:

	def searchInsertK(self, Arr, N, k):
		(lo, hi) = (0, N - 1)
		if k in Arr:
			while lo <= hi:
				mid = (lo + hi) // 2
				if k == Arr[mid]:
					return mid
				elif k > Arr[mid]:
					lo = mid + 1
				else:
					hi = mid - 1
		else:
			while lo <= hi:
				mid = (lo + hi) // 2
				if k < Arr[mid]:
					hi = mid - 1
				else:
					lo = mid + 1
			return lo


class Solution:

	def searchInsertK(self, Arr, N, k):
		for i in range(N):
			if Arr[i] == k:
				return i
			elif Arr[i] > k:
				return i
			elif k > Arr[N - 1]:
				return N


class Solution:

	def searchInsertK(self, Arr, N, k):
		for i in range(0, len(Arr)):
			if Arr[i] == k:
				return i
				break
			elif Arr[i] > k:
				return i
				break
			elif i == len(Arr) - 1:
				return i + 1


import sys

class Solution:

	def searchInsertK(self, Arr, N, k):
		l = 0
		h = N - 1
		maxiE = sys.maxsize
		idx = N
		while l <= h:
			m = (l + h) // 2
			if Arr[m] == k:
				maxiE = k
				idx = m
				break
			elif Arr[m] < k:
				l = m + 1
			else:
				if maxiE > Arr[m]:
					maxiE = Arr[m]
					idx = m
				h = m - 1
		return idx


class Solution:

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


class Solution:

	def searchInsertK(self, Arr, N, k):
		i = 0
		j = N - 1
		if Arr[i] >= k:
			return i
		if Arr[j] < k:
			return N
		if Arr[j] == k:
			return N - 1
		while j >= i:
			mid = (i + j) // 2
			if Arr[i] == k:
				return i
			elif Arr[i] > k:
				return i
			elif Arr[mid] == k:
				return mid
			elif Arr[j] < k:
				return j + 1
			elif Arr[j] == k:
				return j
			elif Arr[mid] > k:
				j = mid - 1
			else:
				i = mid + 1


class Solution(object):

	def searchInsertK(self, nums, N, k):
		(left, right) = (0, N - 1)
		while left <= right:
			mid = (left + right) // 2
			val = nums[mid]
			if val == k:
				return mid
			elif val > k:
				right = mid - 1
			else:
				left = mid + 1
		return left


class Solution:

	def searchInsertK(self, Arr, N, k):
		st = 0
		ed = N - 1
		while st <= ed:
			mid = (st + ed) // 2
			if Arr[mid] == k:
				return mid
			if Arr[mid] > k:
				ed = mid - 1
			else:
				st = mid + 1
		return st


class Solution:

	def searchInsertK(self, Arr, N, k):
		(a, b) = (0, N - 1)
		while a <= b:
			mid = (a + b) // 2
			if Arr[mid] == k:
				index = mid
				return index
				break
			elif Arr[mid] < k:
				a = mid + 1
			else:
				b = mid - 1
		else:
			return a


class Solution:

	def searchInsertK(self, Arr, N, k):
		s = 0
		e = N - 1
		while s <= e:
			m = (s + e) // 2
			if Arr[m] == k:
				return m
			if Arr[m] < k:
				s = m + 1
			else:
				e = e - 1
		return (s + e) // 2 + 1


class Solution:

	def searchInsertK(self, Arr, N, k):
		for i in range(N):
			if Arr[i] == k:
				return i
			if Arr[i] > k:
				return i
		else:
			if Arr[N - 1] < k:
				return N
			else:
				return 0


class Solution:

	def searchInsertK(self, Arr, N, k):
		l = 0
		u = N - 1
		while l <= u:
			mid = (l + u) // 2
			if Arr[mid] == k:
				return mid
			elif Arr[mid] < k:
				l = mid + 1
			else:
				u = mid - 1
		return l


import sys

class Solution:

	def searchInsertK(self, Arr, N, k):
		left = 0
		right = N - 1
		index = sys.maxsize
		if k > Arr[right]:
			return right + 1
		while left <= right:
			mid = (left + right) // 2
			if Arr[mid] == k:
				return mid
			elif Arr[mid] < k:
				left = mid + 1
			else:
				index = min(index, mid)
				right = mid - 1
		return index


class Solution:

	def searchInsertK(self, Arr, N, k):
		(l, r) = (0, len(Arr) - 1)
		while l <= r:
			mid = (l + r) // 2
			if Arr[mid] == k:
				return mid
			elif Arr[mid] < k:
				l = mid + 1
			elif Arr[mid] > k:
				r = mid - 1
		return l


class Solution:

	def searchInsertK(self, Arr, N, k):

		def findindex(A, size, k, r):
			left = r
			right = size - 1
			while left <= right:
				mid = left + (right - left) // 2
				if A[mid] == k:
					return mid
				elif A[mid] < k:
					left = mid + 1
				else:
					right = mid - 1
			return left
		e = findindex(Arr, N, k, 0)
		return e


class Solution:

	def searchInsertK(self, Arr, N, k):
		if k not in Arr:
			Arr.append(k)
		Arr.sort()
		return Arr.index(k)


class Solution:

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


class Solution:

	def searchInsertK(self, Arr, N, k):
		(left, right) = (0, len(Arr) - 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 left


class Solution:

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


class Solution:

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


class Solution:

	def searchInsertK(self, nums, n, target):
		lb = 0
		ub = n - 1
		while lb <= ub:
			mid = (lb + ub) // 2
			if nums[mid] == target:
				return mid
			elif nums[mid] > target:
				ub = mid - 1
			else:
				lb = mid + 1
		return lb


class Solution:

	def searchInsertK(self, arr, n, x):
		l = 0
		h = n - 1
		res = -1
		f = n
		while l <= h:
			mid = (l + h) // 2
			if arr[mid] < x:
				res = mid
				l = mid + 1
			else:
				h = mid - 1
		return res + 1


def lower_bound(A, L, R, k):
	pos = R + 1
	while L <= R:
		M = (L + R) // 2
		if A[M] >= k:
			pos = M
			R = M - 1
		else:
			L = M + 1
	return pos

class Solution:

	def searchInsertK(self, Arr, N, k):
		return lower_bound(Arr, 0, N - 1, k)


class Solution:

	def searchInsertK(self, Arr, N, k):
		if k in Arr:
			return Arr.index(k)
		else:
			for i in range(N):
				if k < Arr[i]:
					Arr.insert(i, k)
					break
				if k > Arr[-1]:
					return N
		return i


class Solution:

	def searchInsertK(self, Arr, N, k):
		s = 0
		e = N - 1
		if k > Arr[e]:
			return N
		if k < Arr[s]:
			return 0
		while s < e:
			mid = (s + e) // 2
			if Arr[mid] == k:
				return mid
			elif Arr[mid] > k:
				e = mid - 1
			else:
				s = mid + 1
		if Arr[s] == k and s == e:
			return s
		if Arr[e] > k and Arr[e - 1] < k:
			return e
		if Arr[e] < k and Arr[e + 1] > k:
			return e + 1
		return mid


class Solution:

	def searchInsertK(self, Arr, N, k):
		o = 0
		if k in Arr:
			return Arr.index(k)
		else:
			for i in Arr:
				if i < k:
					o = o + 1
				if i > k:
					break
			return o


class Solution:

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


class Solution:

	def searchInsertK(self, Arr, N, k):
		l = 0
		h = N - 1
		ans = 0
		if Arr[0] > k:
			return 0
		if Arr[N - 1] < k:
			return N
		while l <= h:
			mid = (l + h) // 2
			if Arr[mid] == k:
				return mid
			if Arr[mid] < k:
				ans = mid + 1
				l = mid + 1
			else:
				h = mid - 1
		return ans


class Solution:

	def searchInsertK(self, Arr, N, K):
		if K in Arr:
			return Arr.index(K)
		else:
			Arr.append(K)
			Arr.sort()
			return Arr.index(K)


class Solution:

	def searchInsertK(self, Arr, N, k):
		return self.helper(Arr, 0, N - 1, k)

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


class Solution:

	def searchInsertK(self, a, n, k):
		if k in a:
			return a.index(k)
		else:
			a.append(k)
			a.sort()
			return a.index(k)


class Solution:

	def searchInsertK(self, A, N, k):
		if A[-1] < k:
			return N
		elif A[-1] == k:
			return N - 1
		if A[0] >= k:
			return 0
		l = 0
		r = N - 1
		mid = 0
		while l <= r:
			mid = (l + r) // 2
			if A[mid] == k:
				return mid
			elif A[mid] < k:
				if A[mid + 1] > k:
					return mid + 1
				else:
					l = mid + 1
			else:
				r = mid - 1


class Solution:

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


class Solution:

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


class Solution:

	def searchInsertK(self, Arr, N, k):
		for i in Arr:
			if i >= k:
				return Arr.index(i)
		return N


class Solution:

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


class Solution:

	def searchInsertK(self, arr, N, k):
		for i in range(N):
			if arr[i] == k:
				return i
			if arr[i] > k:
				return i
		return N


class Solution:

	def searchInsertK(self, Arr, N, k):
		if k in Arr:
			return Arr.index(k)
		else:
			Arr.append(k)
			Arr.sort()
			num = Arr.index(k)
			Arr.remove(k)
			return num