Search insert position of K in a sorted array

The problem is to find the index of K, if it exists in the sorted array arr[], given N unique numbers and an integer K. Find the index where K has to be added to maintain the array sorted otherwise.

Examples

Input: arr[] = {1, 3, 5, 6}, K = 5
Output: 2
Explanation: Since 5 is found at index 2 as arr[2] = 5, the output is 2.


Input: arr[] = {1, 3, 5, 6}, K = 2
Output: 1
Explanation: Since 2 is not present in the array but can be inserted at index 1 to make the array sorted.

Follow the below naive approach to address the issue:

• Go over each element of the array arr[] iteratively looking for integer K.
• Print index of K should any array element be discovered to be equal to K.
• Print that index as the insert location of K else, should any array element turn out to be larger than K. K must be added following the last array element should none of the elements be discovered to be surpassing K.

C++

// C++ program for the above approach

#include <bits/stdc++.h>
using namespace std;

// Function to find insert position of K
int find_index(int arr[], int n, int K)
{
	// Traverse the array
	for (int i = 0; i < n; i++)
		// If K is found
		if (arr[i] == K)
			return i;
		// If current array element exceeds K
		else if (arr[i] > K)
			return i;
	// If all elements are smaller than K
	return n;
}

// Driver Code
int main()
{
	int arr[] = { 1, 3, 5, 6 };
	int n = sizeof(arr) / sizeof(arr[0]);
	int K = 2;
	cout << find_index(arr, n, K) << endl;
	return 0;
}

// This code is contributed by Aditya Kumar (adityakumar129)

C

// C program for the above approach
#include <stdio.h>

// Function to find insert position of K
int find_index(int arr[], int n, int K)
{
	// Traverse the array
	for (int i = 0; i < n; i++)
		// If K is found
		if (arr[i] == K)
			return i;
		// If current array element exceeds K
		else if (arr[i] > K)
			return i;
	// If all elements are smaller than K
	return n;
}

// Driver Code
int main()
{
	int arr[] = { 1, 3, 5, 6 };
	int n = sizeof(arr) / sizeof(arr[0]);
	int K = 2;
	printf("%d\n", find_index(arr, n, K));
	return 0;
}

// This code is contributed by Aditya Kumar (adityakumar129)

Java

// Java program for the above approach
import java.io.*;

class GFG{

// Function to find insert position of K
static int find_index(int[] arr, int n, int K)
{
	
	// Traverse the array
	for(int i = 0; i < n; i++)
	
		// If K is found
		if (arr[i] == K)
			return i;

		// If current array element
		// exceeds K
		else if (arr[i] > K)
			return i;

	// If all elements are smaller
	// than K
	return n;
}

// Driver Code
public static void main(String[] args)
{
	int[] arr = { 1, 3, 5, 6 };
	int n = arr.length;
	int K = 2;
	
	System.out.println(find_index(arr, n, K));
}
}

// This code is contributed by akhilsaini

Python3

# Python program for the above approach

# Function to find insert position of K
def find_index(arr, n, K):
	
	# Traverse the array
	for i in range(n):
		
		# If K is found
		if arr[i] == K:
			return i
			
		# If arr[i] exceeds K
		elif arr[i] > K:
			return i
			
	# If all array elements are smaller
	return n

# Driver Code
arr = [1, 3, 5, 6]
n = len(arr)
K = 2
print(find_index(arr, n, K))

C#

// C# program for the above approach
using System;

class GFG{

// Function to find insert position of K
static int find_index(int[] arr, int n, int K)
{
	
	// Traverse the array
	for(int i = 0; i < n; i++)
	
		// If K is found
		if (arr[i] == K)
			return i;

		// If current array element
		// exceeds K
		else if (arr[i] > K)
			return i;

	// If all elements are smaller
	// than K
	return n;
}

// Driver Code
public static void Main()
{
	int[] arr = { 1, 3, 5, 6 };
	int n = arr.Length;
	int K = 2;
	
	Console.WriteLine(find_index(arr, n, K));
}
}

// This code is contributed by akhilsaini

JavaScript

<script>

// Javascript program for the above approach

// Function to find insert position of K
function find_index(arr, n, K)
{
	
	// Traverse the array
	for(let i = 0; i < n; i++)
	
		// If K is found
		if (arr[i] == K)
			return i;

		// If current array element
		// exceeds K
		else if (arr[i] > K)
			return i;

	// If all elements are smaller
	// than K
	return n;
}

// Driver code
let arr = [ 1, 3, 5, 6 ];
let n = arr.length;
let K = 2;

document.write(find_index(arr, n, K));

// This code is contributed by splevel62 

</script>

Output

1
Time Complexity: O(N)
Auxiliary Space: O(1)

Binary Search is the suggested method to maximize the above one.

Use the following procedures to tackle the issue:

• Set start and finish as 0 and N – 1; where the start and end variables respectively indicate the bottom and upper bound of the search space.
• Mid = (start + end) / 2.
• Print mid as the necessary response should arr[mid] prove to be equal to K.
• Should arr[mid] be greater than K, set high = mid – 1. Otherwise define low as mid + 1.
• The aforesaid strategy is implemented here below:

C++

// C++ program for the above approach

#include <bits/stdc++.h>
using namespace std;

// Function to find insert position of K
int find_index(int arr[], int n, int K)
{
	// Lower and upper bounds
	int start = 0;
	int end = n - 1;
	// Traverse the search space
	while (start <= end) {
		int mid = (start + end) / 2;
		// If K is found
		if (arr[mid] == K)
			return mid;
		else if (arr[mid] < K)
			start = mid + 1;
		else
			end = mid - 1;
	}
	// Return insert position
	return end + 1;
}

// Driver Code
int main()
{
	int arr[] = { 1, 3, 5, 6 };
	int n = sizeof(arr) / sizeof(arr[0]);
	int K = 2;
	cout << find_index(arr, n, K) << endl;
	return 0;
}

// This code is contributed by Aditya Kumar (adityakumar129)

C

// C program for the above approach

#include<stdio.h>

// Function to find insert position of K
int find_index(int arr[], int n, int K)
{
	// Lower and upper bounds
	int start = 0;
	int end = n - 1;
	// Traverse the search space
	while (start <= end) {
		int mid = (start + end) / 2;
		// If K is found
		if (arr[mid] == K)
			return mid;
		else if (arr[mid] < K)
			start = mid + 1;
		else
			end = mid - 1;
	}
	// Return insert position
	return end + 1;
}

// Driver Code
int main()
{
	int arr[] = { 1, 3, 5, 6 };
	int n = sizeof(arr) / sizeof(arr[0]);
	int K = 2;
	printf("%d",find_index(arr, n, K));
	return 0;
}

// This code is contributed by Aditya Kumar (adityakumar129)

Java

// Java program for the above approach
import java.io.*;

class GFG{

// Function to find insert position of K
static int find_index(int[] arr, int n, int K)
{
	
	// Lower and upper bounds
	int start = 0;
	int end = n - 1;

	// Traverse the search space
	while (start <= end) 
	{
		int mid = (start + end) / 2;

		// If K is found
		if (arr[mid] == K)
			return mid;

		else if (arr[mid] < K)
			start = mid + 1;

		else
			end = mid - 1;
	}

	// Return insert position
	return end + 1;
}

// Driver Code
public static void main(String[] args)
{
	int[] arr = { 1, 3, 5, 6 };
	int n = arr.length;
	int K = 2;
	
	System.out.println(find_index(arr, n, K));
}
}

// This code is contributed by akhilsaini

Python3

# Python program to implement
# the above approach

# Function to find insert position of K
def find_index(arr, n, K):

	# Lower and upper bounds
	start = 0
	end = n - 1

	# Traverse the search space
	while start<= end:

		mid =(start + end)//2

		if arr[mid] == K:
			return mid

		elif arr[mid] < K:
			start = mid + 1
		else:
			end = mid-1

	# Return the insert position
	return end + 1

# Driver Code
arr = [1, 3, 5, 6]
n = len(arr)
K = 2
print(find_index(arr, n, K))

C#

// C# program for the above approach
using System;

class GFG{

// Function to find insert position of K
static int find_index(int[] arr, int n, int K)
{
	
	// Lower and upper bounds
	int start = 0;
	int end = n - 1;

	// Traverse the search space
	while (start <= end) 
	{
		int mid = (start + end) / 2;

		// If K is found
		if (arr[mid] == K)
			return mid;

		else if (arr[mid] < K)
			start = mid + 1;

		else
			end = mid - 1;
	}

	// Return insert position
	return end + 1;
}

// Driver Code
public static void Main()
{
	int[] arr = { 1, 3, 5, 6 };
	int n = arr.Length;
	int K = 2;
	
	Console.WriteLine(find_index(arr, n, K));
}
}

// This code is contributed by akhilsaini

JavaScript

<script>
// JavaScript program for the above approach

// Function to find insert position of K
function find_index(arr, n, K)
{
	// Lower and upper bounds
	let start = 0;
	let end = n - 1;

	// Traverse the search space
	while (start <= end) {
		let mid = Math.floor((start + end) / 2);

		// If K is found
		if (arr[mid] == K)
			return mid;

		else if (arr[mid] < K)
			start = mid + 1;

		else
			end = mid - 1;
	}

	// Return insert position
	return end + 1;
}

// Driver Code
	let arr = [ 1, 3, 5, 6 ];
	let n = arr.length;
	let K = 2;
	document.write(find_index(arr, n, K) + "<br>");




// This code is contributed by Surbhi Tyagi.
</script>

Output

1
Time Complexity: O(log N)
Auxiliary Space: O(1)