BlogsDope image BlogsDope

Search insert position of K in a sorted array

March 21, 2021 JAVA ARRAY ALGORITHM DATA STRUCTURE 7648

Problem Statement

Given a sorted array arr[] consisting of N distinct integers and an integer K, the task is to find the index of K, if it is present in the array arr[]. Otherwise, find the index where K must be inserted to keep the array sorted.

Example

  • Input: A[]={1,2,3,4,5} k=4

       Output:3           //4 is at 3rd position

  • Input: A[]={1,2,4,5} k=3

       Output:2          //2 is the index position where k must be inserted to keep the array sorted

Approach

Before we discuss the approach for this question let’s see what exactly the question requires us to do. It seems that we have to find the index position of the sorted array where k is present. In case, if k is not present in the array then we need to find the position where k must be inserted to keep the array sorted.

The basic approach can be to first traverse through the whole array if k is found at any index position return index. Otherwise, if the array element is greater than k then insert k at that position to keep the array sorted  and return index.

Pseudocode

function search(array,k)
   for i in 0 to array.length
       if array element is equal to k
          return i
       if array element is greater than k
          return i
  • Make a function named search and, input an array and k.
  • Traverse through the array and check whether the element is equal to k or not.
  • If the element is equal to k then return index position of the element.
  • And  if the element is greater than k then also return the index position of the element to insert the value of k at that position for keeping the array sorted.

Program

package codesdope;
import java.util.*;
public class codesdope 
{
	public static int search(int arr[],int x)
	{
		for(int i=0;i<arr.length;i++)
		{
			if(arr[i]==x)
				return i;
			if(arr[i]>x)
				return i;
		}
		return -1;
	}
	public static void main(String[] args) 
	{
		int arr[]= {1,2,3,4,5,6,8,9};
		System.out.println(search(arr,2));
		System.out.println(search(arr,7));
	}
}

6

Let us dry run the above code-
arr[]={1,2,3,4,5,6,8,9}
  • When K=2
       i=0  arr[0]!=2   
       i=0  arr[0] is not greater than 2
       i=1  arr[1]=2
       return 1
OUTPUT=1
  • When k=7
       i=0 arr[0]!=7
       i=0 arr[0] is not greater than 7
       i=1 arr[1]!=7
       i=1 arr[1] is not greater than 7
       i=2 arr[2]!=7 
       i=2 arr[2] is not greater than 7
       i=3 arr[3]!=7 
       i=3 arr[3] is not greater than 7
       i=4 arr[4]!=7 
       i=4 arr[4] is not greater than 7
       i=5 arr[5]!=7 
       i=5 arr[5] is not greater than 7
       i=6 arr[6]!=7 
       i=6 arr[6] is greater than 7=return 6
       Output=6

Time Complexity

Since we will be traversing the whole array therefore the time complexity of algorithm would be O(N).

Liked the post?
Editor's Picks
0 COMMENT

Please login to view or add comment(s).