Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in Java

Solution: Search Insert Position

Explore how to implement a modified binary search to solve the Search Insert Position problem. Understand how adjusting pointers and tracking the mid position allows you to efficiently determine the correct index for a target value in a sorted array, with optimal logarithmic time complexity.

We'll cover the following...

Solution: Modified binary search

Java
class SearchInsert
{ 
  public static int insertPosition(int[] arr, int target) 
  {   
    int arrSize = arr.length;
    //checking of size of array is less than 1
    if(arrSize < 1)
        return -1;  
    int start = 0;
    int end = arrSize - 1;
    int mid = 0, pos = 0;
    //traversing the array
    while(start <= end) 
    {
        //calculating the mid value
        mid = start + (end-start)/2;  
        //if mid value equals target return the mid index   
        if(arr[mid] == target)
        return mid;
        //if mid value greater than target serach in the left half 
        else if(arr[mid] > target)
        {
            end = mid - 1;
            pos = mid;
        } 
        //otherwise search in the right half
        else 
        {
            start = mid + 1;
            pos = mid + 1;
        }
    }
    return pos;
  }
  public static void main(String args[]) 
  {
    int[]arr = {0, 1, 2, 3, 5, 6};
    
    // Example 1
    System.out.println("Index to Insert " + "\"5\" is " + insertPosition(arr, 5));
    
    // Example 2
    System.out.println("Index to Insert " + "\"3\" is " + insertPosition(arr, 3));
    // Example 3
    System.out.println("Index to Insert " + "\"7\" is " + insertPosition(arr, 7));  
  }
}

This solution is a simple modification of the binary search algorithm. It simply keeps track of the variable mid with another one called pos. It starts by traversing the array and calculating the mid value (lines 13 & 16). If it equals target, it simply ...