thesarfo

Reference

Search Insert Position

Returning a target's index if present, or its insertion index otherwise — exactly the lower bound problem.

views 0

Return the index of target if present, otherwise the index where it would be inserted to keep the array sorted — this is exactly the lower bound problem. (LeetCode 35)

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;


        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;  // Exact match found
            } else if (nums[mid] > target) {
                right = mid - 1;  // Narrow search to the left
            } else {
                left = mid + 1;  // Narrow search to the right
            }
        }
        return left;  // `left` ends up being the insertion point
    }
}

left converges to the first index where nums[i] >= target, so it doubles as both the exact match position and the insertion point — no separate ans variable needed. For nums = [1,3,5,6], target = 5: mid=1 (nums[1]=3 < 5, left=2), mid=2 (nums[2]=5 == 5, return 2).