# Given a sorted array/vector/list of distinct integers and a target value K,
# return the index if the target is found.
# If not, return the index where it would be if inserted in order.
# Function to find the index of k or the position where it should be inserted - Using Binary Search
def search_insert_position(lst, k):
left, right = 0, len(lst) - 1
while left <= right:
mid = left + (right - left) // 2
if lst[mid] == k:
return mid
# If k is smaller, search in the left half
elif lst[mid] > k:
right = mid - 1
# If k is larger, search in the right half
else:
left = mid + 1
# If k is not found, return the index where it should be inserted
return left
list1 = [1, 3, 5, 6, 7, 8]
k1 = 5
print(search_insert_position(list1, k1))
list2 = [1, 3, 5, 6, 7, 8]
k2 = 2
print(search_insert_position(list2, k2))
list3 = [1, 3, 5, 6, 7, 8]
k3 = 9
print(search_insert_position(list3, k3))
'''
run:
2
1
6
'''