Question

How to search insert position of K in a sorted list with Python

Answer 1

# 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
def search_insert_position(lst, k):
    for i in range(len(lst)):
        # If k is found or needs to be inserted before lst[i]
        if lst[i] >= k:
            return i
    # If k is greater than all elements, it should be inserted at the end
    return len(lst)


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

'''

 

Learn SQL from A to Z at LearnSQL.com

Answer 2

# 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

'''

 

Learn SQL from A to Z at LearnSQL.com