Search Insert Position in Sorted Array (Lower Bound Approach)

Given a sorted array of distinct integers and a target number x, your task is to find the insert position of x.

This means you must return the index where x is located in the array. If it is not present, return the index where it should be inserted in order to keep the array sorted.

This problem is also known as finding the lower bound — the first index where an element is greater than or equal to x.

Understanding the Problem

Suppose you are given a sorted array, and you want to find the correct position to insert a target number x so that the array remains sorted. This problem is not just about checking if x is present; it's about finding the position where it could be inserted — this is called the lower bound.

For example, if arr = [1, 3, 5, 6] and x = 5, the output should be 2 because 5 is already at index 2.

But if x = 4, then the correct insert position is 2 because it would go between 3 and 5.

Step-by-Step Intuition

Let’s solve this using a technique called binary search, which is perfect for sorted arrays. Instead of checking every position one by one, we’ll divide the array in halves, zero in on the region where x could go, and find the first index where arr[i] ≥ x.

Step 1: Initialize Search Range

We start with two pointers:

• low = 0 (start of the array)
• high = n - 1 (end of the array)

We also define ans = n (default answer is the end of array, in case x is greater than all elements).

Step 2: Binary Search Loop

Repeat while low ≤ high:

• Calculate mid = Math.floor((low + high) / 2)
• If arr[mid] ≥ x:
  • This index might be the correct insert position, so set ans = mid
  • Move search to the left half: high = mid - 1
• Else:
  • x is greater than arr[mid], so move right: low = mid + 1

Step 3: Final Answer

After the loop ends, ans will hold the first index where x can be inserted to maintain the sorted order.

Example Walkthrough

Let’s try with arr = [1, 3, 5, 6] and x = 4.

• low = 0, high = 3
• mid = 1 → arr[1] = 3 → 3 < 4 → move right → low = 2
• mid = 2 → arr[2] = 5 → 5 ≥ 4 → ans = 2, high = 1
• Loop ends → Final answer: 2

Handling Edge Cases

• x is smaller than all elements → e.g., x = 0 → insert at index 0
• x is greater than all elements → e.g., x = 10 → insert at index arr.length
• x is equal to an existing value → insert at the first occurrence (lower bound)

Why Binary Search?

Binary search gives us an efficient way to solve this in O(log n) time instead of scanning every element. This is especially useful for large arrays.

1. Given a sorted array arr of distinct integers and a target value x.
2. Initialize: low = 0, high = arr.length - 1, ans = arr.length.
3. While low ≤ high:
4. → Compute mid = Math.floor((low + high) / 2).
5. → If arr[mid] ≥ x, update ans = mid and move left: high = mid - 1.
6. → Else, move right: low = mid + 1.
7. Return ans as the correct insert position.

#include <stdio.h>

int searchInsertPosition(int arr[], int size, int target) {
  int low = 0, high = size - 1, ans = size;
  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (arr[mid] >= target) {
      ans = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return ans;
}

int main() {
  int arr[] = {1, 3, 5, 6};
  int size = sizeof(arr) / sizeof(arr[0]);
  int target = 2;
  printf("Insert Position: %d\n", searchInsertPosition(arr, size, target));
  return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int searchInsertPosition(vector<int>& arr, int target) {
  int low = 0, high = arr.size() - 1, ans = arr.size();
  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (arr[mid] >= target) {
      ans = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return ans;
}

int main() {
  vector<int> arr = {1, 3, 5, 6};
  int target = 2;
  cout << "Insert Position: " << searchInsertPosition(arr, target) << endl;
  return 0;
}

def search_insert_position(arr, x):
    n = len(arr)
    low, high = 0, n - 1
    ans = n
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] >= x:
            ans = mid
            high = mid - 1
        else:
            low = mid + 1
    return ans

# Sample Input
arr = [1, 3, 5, 6]
target = 2
print("Insert Position:", search_insert_position(arr, target))

public class SearchInsertPosition {
  public static int searchInsert(int[] arr, int target) {
    int low = 0, high = arr.length - 1, ans = arr.length;
    while (low <= high) {
      int mid = (low + high) / 2;
      if (arr[mid] >= target) {
        ans = mid;
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    return ans;
  }

  public static void main(String[] args) {
    int[] arr = {1, 3, 5, 6};
    int target = 2;
    System.out.println("Insert Position: " + searchInsert(arr, target));
  }
}

function searchInsertPosition(arr, target) {
  let low = 0, high = arr.length - 1;
  let ans = arr.length;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (arr[mid] >= target) {
      ans = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return ans;
}

// Sample Input
const arr = [1, 3, 5, 6];
const target = 2;
console.log("Insert Position:", searchInsertPosition(arr, target));

package main

import (
  "fmt"
)

func searchInsertPosition(arr []int, target int) int {
  low, high := 0, len(arr)-1
  ans := len(arr)
  for low <= high {
    mid := (low + high) / 2
    if arr[mid] >= target {
      ans = mid
      high = mid - 1
    } else {
      low = mid + 1
    }
  }
  return ans
}

func main() {
  arr := []int{1, 3, 5, 6}
  target := 2
  fmt.Println("Insert Position:", searchInsertPosition(arr, target))
}

fn search_insert_position(arr: &Vec<i32>, target: i32) -> usize {
    let (mut low, mut high) = (0, arr.len() as i32 - 1);
    let mut ans = arr.len();
    while low <= high {
        let mid = low + (high - low) / 2;
        if arr[mid as usize] >= target {
            ans = mid as usize;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    ans
}

fn main() {
    let arr = vec![1, 3, 5, 6];
    let target = 2;
    println!("Insert Position: {}", search_insert_position(&arr, target));
}

fun searchInsertPosition(arr: IntArray, target: Int): Int {
    var low = 0
    var high = arr.size - 1
    var ans = arr.size
    while (low <= high) {
        val mid = (low + high) / 2
        if (arr[mid] >= target) {
            ans = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return ans
}

fun main() {
    val arr = intArrayOf(1, 3, 5, 6)
    val target = 2
    println("Insert Position: ${searchInsertPosition(arr, target)}")
}

func searchInsertPosition(_ arr: [Int], _ target: Int) -> Int {
    var low = 0, high = arr.count - 1
    var ans = arr.count
    while low <= high {
        let mid = (low + high) / 2
        if arr[mid] >= target {
            ans = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return ans
}

let arr = [1, 3, 5, 6]
let target = 2
print("Insert Position:", searchInsertPosition(arr, target))

function searchInsertPosition(arr: number[], target: number): number {
  let low = 0, high = arr.length - 1;
  let ans = arr.length;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (arr[mid] >= target) {
      ans = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return ans;
}

const arr: number[] = [1, 3, 5, 6];
const target: number = 2;
console.log("Insert Position:", searchInsertPosition(arr, target));

Time complexity

Space complexity

O(1)

The algorithm operates in-place using only a constant amount of memory — just a few integer variables for low, high, mid, and ans.