35. Search Insert Position | LeetCode [Solved + Explanation] Easy Method Explained

35. Search Insert Position  [Solved + Explanation] Easy Method Explained

Problem :

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [1,3,5,6], target = 5

Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2

Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7

Output: 4

Constraints:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums contains distinct values sorted in ascending order.
• -10^4 <= target <= 10^4

Solution :

We'll employ the lower-bound algorithm, essentially a tailored version of the classic Binary Search algorithm, to address this issue.
Binary Search aims to efficiently identify the appropriate half to discard, thereby halving the search space. It achieves this by establishing a specific condition ensuring the target's absence in that half.
Upon thorough examination of the problem, it becomes apparent that our objective is to locate the precise or existing position of the target number within the given array.
Should the element be absent, our aim shifts to identifying the nearest greater number to the target. Essentially, we seek an element `arr[ind] >= x`, indicating the lower bound of the target number, `x`.
The lower-bound algorithm yields the first occurrence of the target number if present; otherwise, it returns the nearest greater element to the target number.

Approach:

Here's our methodology:

• Initialization: We'll set up two pointers and an 'ans' variable, initialized to 'n', the array's size (as 'n' will be returned if no index is found).
• Pointer Placement: Initially, position the pointers as follows: 'low' points to the first index, and 'high' points to the last index.
• Mid Calculation: Compute the value of 'mid' using the formula: `mid = (low+high) // 2` (where '//' denotes integer division).
• Comparison with 'x': Compare 'arr[mid]' with 'x'. This yields two distinct scenarios:
• Case 1: If 'arr[mid] >= x', indicating that 'mid' may be a potential answer, update the 'ans' variable with 'mid'. Then, search the left half for any smaller indices satisfying the same condition, effectively eliminating the right half.
• Case 2: If 'arr[mid] < x', 'mid' cannot serve as the answer, necessitating the search for a larger element. Eliminate the left half and explore the right half for the solution.
• Repeat the above process until the 'low' pointer surpasses 'high'.

Code:

C++ Code:

int searchInsert(vector& arr, int x) {
    int n = arr.size(); // size of the array
    int low = 0, high = n - 1;
    int ans = n;

    while (low <= high) {
        int mid = (low + high) / 2;
        // maybe an answer
        if (arr[mid] >= x) {
            ans = mid;
            //look for smaller index on the left
            high = mid - 1;
        }
        else {
            low = mid + 1; // look on the right
        }
    }
    return ans;
}

Java Code:

public class Main {

    public static int searchInsert(int [] arr, int x) {
        int n = arr.length; // size of the array
        int low = 0, high = n - 1;
        int ans = n;

        while (low <= high) {
            int mid = (low + high) / 2;
            // maybe an answer
            if (arr[mid] >= x) {
                ans = mid;
                //look for smaller index on the left
                high = mid - 1;
            } else {
                low = mid + 1; // look on the right
            }
        }
        return ans;
    }

Python Code:

def searchInsert(arr: [int], x: int) -> int:
    n = len(arr)  # size of the array
    low = 0
    high = n - 1
    ans = n

    while low <= high:
        mid = (low + high) // 2
        # maybe an answer
        if arr[mid] >= x:
            ans = mid
            # look for smaller index on the left
            high = mid - 1
        else:
            low = mid + 1  # look on the right

    return ans

Complexity:

Time Complexity: O(logN), where N = size of the given array.

Reason: We are basically using the Binary Search algorithm.

Space Complexity: O(1) as we are using no extra space.

I hope this solution helps you :-)

Keywords :- 

• leetcode solutions python,
• leetcode solutions two sum,
• Leetcode solutions pdf,
• Leetcode solutions java,
• leetcode solutions in c,
• Leetcode solutions github,
• leetcode solutions extension,
• leetcode solutions javascript,
• leetcode solutions c++ pdf,
• Leetcode solutions c++ github,
• leetcode problems and solutions pdf,
• Leetcode solutions c++ example,
• leetcode c++ easy,
• leetcode solutions java,
• leetcode problems and solutions java pdf,
• leetcode-solutions github,