Given a 0 based sorted array arr[] of distinct integers and an integer k, find the index of k if it is present. If not, return the index where k should be inserted to maintain the sorted order.
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: The element 2 is not present in the array, but inserting it at index 1 will maintain the sorted order.
Try it on GfG Practice
Table of Content
[Naive Approach] Traverse and Find - O(n) Time and O(1) Space
The idea is to iterate through the array and find the first position where k is less than or equal to arr[i] (current element). We traverse the array linearly, checking each element to determine if k should be placed at or before it. If k is larger than all elements, it is inserted at the end, returning the array size.
#include <iostream>
#include <vector>
using namespace std;
int searchInsertK(vector<int> arr, int k) {
for(int i = 0; i < arr.size(); i++) {
// if k is found or needs to be
// inserted before arr[i]
if(arr[i] >= k) {
return i;
}
}
// if k is greater than all
// elements insert at the end
return arr.size();
}
int main() {
vector<int> arr = {1, 3, 5, 6};
int k = 5;
cout << searchInsertK(arr, k) << endl;
return 0;
}
class GfG {
static int searchInsertK(int arr[], int k) {
for(int i = 0; i < arr.length; i++) {
// if k is found or needs to be inserted
// before arr[i]
if(arr[i] >= k) {
return i;
}
}
// if k is greater than all elements,
// insert at the end
return arr.length;
}
public static void main(String args[]) {
int arr[] = {1, 3, 5, 6};
int k = 5;
System.out.println(searchInsertK(arr, k));
}
}
def searchInsertK(arr, k):
for i in range(len(arr)):
# if k is found or needs to be inserted
# before arr[i]
if arr[i] >= k:
return i
# if k is greater than all elements,
# insert at the end
return len(arr)
if __name__ == "__main__":
arr = [1, 3, 5, 6]
k = 5
print(searchInsertK(arr, k))
using System;
class GfG {
static int searchInsertK(int[] arr, int k) {
for(int i = 0; i < arr.Length; i++) {
// if k is found or needs to be
// inserted before arr[i]
if(arr[i] >= k) {
return i;
}
}
// if k is greater than all elements,
// insert at the end
return arr.Length;
}
public static void Main() {
int[] arr = {1, 3, 5, 6};
int k = 5;
Console.WriteLine(searchInsertK(arr, k));
}
}
function searchInsertK(arr, k) {
for(let i = 0; i < arr.length; i++) {
// if k is found or needs to be
// inserted before arr[i]
if(arr[i] >= k) {
return i;
}
}
// if k is greater than all elements,
// insert at the end
return arr.length;
}
// Driver Code
let arr = [1, 3, 5, 6];
let k = 5;
console.log(searchInsertK(arr, k));
Output
2
[Expected Approach] Using Binary Search - O(log n) Time and O(1) Space
The idea is to use binary search, instead of scanning the entire array linearly. The thought process begins by recognizing that a sorted array allows us to use binary search.
=> We use two pointers (left and right) to narrow down the search space by comparing k with the middle element, halving the problem at each step.
=> If k is found, return its index; otherwise, the left pointer will naturally point to the correct insertion position when the search ends.
#include <iostream>
#include <vector>
using namespace std;
int searchInsertK(vector<int> arr, int k) {
int left = 0, right = arr.size() - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
// if k is found at mid
if(arr[mid] == k) {
return mid;
}
// if k is smaller, search in left half
else if(arr[mid] > k) {
right = mid - 1;
}
// if k is larger, search in right half
else {
left = mid + 1;
}
}
// if k is not found, return insert position
return left;
}
int main() {
vector<int> arr = {1, 3, 5, 6};
int k = 5;
cout << searchInsertK(arr, k) << endl;
return 0;
}
class GfG {
static int searchInsertK(int arr[], int k) {
int left = 0, right = arr.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
// if k is found at mid
if(arr[mid] == k) {
return mid;
}
// if k is smaller, search in left half
else if(arr[mid] > k) {
right = mid - 1;
}
// if k is larger, search in right half
else {
left = mid + 1;
}
}
// if k is not found, return insert position
return left;
}
public static void main(String args[]) {
int arr[] = {1, 3, 5, 6};
int k = 5;
System.out.println(searchInsertK(arr, k));
}
}
def searchInsertK(arr, k):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
# if k is found at mid
if arr[mid] == k:
return mid
# if k is smaller, search in left half
elif arr[mid] > k:
right = mid - 1
# if k is larger, search in right half
else:
left = mid + 1
# if k is not found, return insert position
return left
if __name__ == "__main__":
arr = [1, 3, 5, 6]
k = 5
print(searchInsertK(arr, k))
using System;
class GfG {
static int searchInsertK(int[] arr, int k) {
int left = 0, right = arr.Length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
// if k is found at mid
if(arr[mid] == k) {
return mid;
}
// if k is smaller, search in left half
else if(arr[mid] > k) {
right = mid - 1;
}
// if k is larger, search in right half
else {
left = mid + 1;
}
}
// if k is not found, return insert position
return left;
}
public static void Main() {
int[] arr = {1, 3, 5, 6};
int k = 5;
Console.WriteLine(searchInsertK(arr, k));
}
}
function searchInsertK(arr, k) {
let left = 0, right = arr.length - 1;
while(left <= right) {
let mid = left + Math.floor((right - left) / 2);
// if k is found at mid
if(arr[mid] === k) {
return mid;
}
// if k is smaller, search in left half
else if(arr[mid] > k) {
right = mid - 1;
}
// if k is larger, search in right half
else {
left = mid + 1;
}
}
// if k is not found, return insert position
return left;
}
// Driver Code
let arr = [1, 3, 5, 6];
let k = 5;
console.log(searchInsertK(arr, k));
Output
2
[Alternate Approach] Using Binary Search - O(log n) Time and O(1) Space
The idea is to refine the traditional binary search by ensuring that we always land on the first position where the target could be inserted. Unlike the previous approach, here we eliminate elements from the right by setting right = mid instead of right = mid - 1, ensuring left never skips a potential insert position.
This guarantees that when the loop ends, left directly points to the first index where k should be placed. The final check ensures that if arr[left] is still smaller than k, we return left + 1, otherwise, we return left.
#include <iostream>
#include <vector>
using namespace std;
int searchInsertK(vector<int> arr, int k) {
int left = 0, right = arr.size() - 1;
while(left < right) {
int mid = left + (right - left) / 2;
// if arr[mid] is less than k, move to
// the right part
if(arr[mid] < k) {
left = mid + 1;
}
// otherwise, move to the left part
else {
right = mid;
}
}
// found place: arr[left] is the first element >= k
return (arr[left] < k) ? left + 1 : left;
}
int main() {
vector<int> arr = {1, 3, 5, 6};
int k = 5;
cout << searchInsertK(arr, k) << endl;
return 0;
}
class GfG {
static int searchInsertK(int arr[], int k) {
int left = 0, right = arr.length - 1;
while(left < right) {
int mid = left + (right - left) / 2;
// if arr[mid] is less than k, move to
// the right part
if(arr[mid] < k) {
left = mid + 1;
}
// otherwise, move to the left part
else {
right = mid;
}
}
// found place: arr[left] is the first element >= k
return (arr[left] < k) ? left + 1 : left;
}
public static void main(String args[]) {
int arr[] = {1, 3, 5, 6};
int k = 5;
System.out.println(searchInsertK(arr, k));
}
}
def searchInsertK(arr, k):
left, right = 0, len(arr) - 1
while left < right:
mid = left + (right - left) // 2
# if arr[mid] is less than k, move to
# the right part
if arr[mid] < k:
left = mid + 1
# otherwise, move to the left part
else:
right = mid
# found place: arr[left] is the first element >= k
return left + 1 if arr[left] < k else left
if __name__ == "__main__":
arr = [1, 3, 5, 6]
k = 5
print(searchInsertK(arr, k))
using System;
class GfG {
static int searchInsertK(int[] arr, int k) {
int left = 0, right = arr.Length - 1;
while(left < right) {
int mid = left + (right - left) / 2;
// if arr[mid] is less than k, move to
// the right part
if(arr[mid] < k) {
left = mid + 1;
}
// otherwise, move to the left part
else {
right = mid;
}
}
// found place: arr[left] is the first element >= k
return (arr[left] < k) ? left + 1 : left;
}
public static void Main() {
int[] arr = {1, 3, 5, 6};
int k = 5;
Console.WriteLine(searchInsertK(arr, k));
}
}
function searchInsertK(arr, k) {
let left = 0, right = arr.length - 1;
while (left < right) {
let mid = left + Math.floor((right - left) / 2);
// if arr[mid] is less than k, move to
// the right part
if (arr[mid] < k) {
left = mid + 1;
}
// otherwise, move to the left part
else {
right = mid;
}
}
// found place: arr[left] is the first element >= k
return arr[left] < k ? left + 1 : left;
}
// Driver code
const arr = [1, 3, 5, 6];
const k = 5;
console.log(searchInsertK(arr, k));
Output
2