Search insert position of K in a sorted array Geeks For Geeks

 Problem Link:

(It is also the problem of the day for 23-04-2022)

Solution:

class Solution

{

    static int searchInsertK(int arr[], int n, int k)

    {

        boolean flag=true;

        int pos=0;

        for(int i=0;i<n;i++){

            if(arr[i]==k){

                flag=false;

                pos=i;

            }

        }

        if(flag==true){

            for(int i=0;i<arr.length-1;i++){

                if(arr[i]<k && k<arr[i+1]){

                    pos=i+1;

                    break;

                }

                else if(k>arr[arr.length-1]){

                    pos=arr.length;

                }

                else if(k<arr[0]){

                    pos=0;

                }

            }

            return pos;

        }

        else{

            return pos;

        }

        

    }

}

Total Test Cases:304

Time Complexity:   O(N)[GFG Time:0.44/3.09][Linear Search]

Space Complexity: O(N)[Array is given.]

Auxiliary Space: O(1)

Approach Used:

Here first of all we will traverse the array and if we found an element then we will return its index, or if not then we will traverse the array another time and check for 3 cases:

1. if the element to be searched has a value within the array means it is greater than some element in the array and smaller than the next element in the array then return index+1

2. if its value is smaller than the 0th element of the array then return 0

3. If its value is more than the last element of the array then return arr. length

boolean flag=true is used to check the status of an element's presence in the array.

While the first iteration, if an element is present in the array flag, will change and become false, otherwise it will remain true.

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"