BudiBadu Logo

Search Insert Position

Binary Search Easy 11 views
Like21

You’re given a list of distinct integers in ascending order and a target number. Your mission in Search Insert Position is to find where that target belongs. If it’s in the list, return its index. If missing, find the index where it should be inserted to keep the sequence perfectly sorted.

The "secret sauce" is Binary Search. While you could scan from front to back, a sorted list allows you to find the position much faster by repeatedly halving your search area. This results in a lightning-fast O(log n) complexity! You must handle cases where the target is smaller or larger than every element, or falls between two values. This challenge is a fundamental test of your ability to manage ordered data and boundary conditions efficiently. It turns a simple "Look up" task into a masterclass in sequence management!

If sorting is part of the strategy, do it intentionally as a preprocessing step to simplify downstream logic such as merging, ordering, or comparison. After sorting, keep output semantics precise: preserve expected structure, avoid dropping valid entries, and ensure tied cases still follow deterministic order rules.

Examples

Example 1
Input
nums = [1,3,5,6], target = 5
Output
2
Explanation

The number 5 already exists in the list and is located at index 2.

Example 2
Input
nums = [1,3,5,6], target = 2
Output
1
Explanation

The target 2 is not in the list but would fit between 1 and 3, so its position would be index 1.

Example 3
Input
nums = [1,3,5,6], target = 7
Output
4
Explanation

The target 7 is greater than all elements, so it should appear at the end, which corresponds to index 4.

Algorithm Flow

Recommendation Algorithm Flow for Search Insert Position - Budibadu
Recommendation Algorithm Flow for Search Insert Position - Budibadu

Best Answers

java
class Solution {
    public int search_insert(Object nums, Object target) {
        int[] arr = (int[]) nums;
        int t = (int) target;
        int left = 0;
        int right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < t) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}