Search insert position of K in a sorted array

 

PROBLEM 57: Search insert position of K in a sorted array

(For best view experience, view in windows version)

Problem Reference : GeeksForGeeks

Author : Ajay Zad

Date    : 20/04/2023

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.

SOLUTION:

class Solution:
    def searchInsertK(self, Arr, N, k):
        # code here
        if k in Arr:
            a = Arr.index(k)
            return a
        else:
            cnt = 0
            for i in Arr:
                if i < k:
                    cnt = cnt + 1
                else:
                    return cnt
            else:
                return len(Arr)


if __name__ == '__main__':
    t = int(input())
    for _ in range (t):
        N = int(input())
        Arr = input().split()
        for itr in range(N):
            Arr[itr] = int(Arr[itr])
        k = int(input())
        ob = Solution()
        print(ob.searchInsertK(Arr, N, k))

Expected Time Complexity: O(logN)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ N ≤ 104
-103 ≤ Arr[i] ≤ 103
-103 ≤ k ≤ 103