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));
}
}
1
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).