Search Insert Position in a Sorted Array

You are given an array of integers sorted in strictly increasing order, and a target value. Return the index at which the target would be found if it is present in the array. If it is not present, return the index where it should be inserted so the array remains sorted in strictly increasing order. Your algorithm must run in O(log n) time.

Input: The first line contains the integer n. The second line contains n space-separated integers, the sorted array. The third line contains the integer target. Output: Print a single integer: the index (0-indexed) where target is found, or where it should be inserted.

1 <= n <= 10^5 -10^9 <= arr[i], target <= 10^9 arr is sorted in strictly increasing order and contains distinct elements.

Setting the search range's upper bound to n (not n-1) is what correctly allows 'insert at the very end' as a valid answer - a common off-by-one trap if the range is set up carelessly.

Find where a target value sits (or would sit) in a sorted array, using binary search. Brute force: Scan the array linearly looking for the target or the first element bigger than it - this costs O(n), unnecessary given the array's sorted structure, which allows binary search. Optimised: Framing this as 'find the first position where arr[pos] >= target' (rather than treating found/not-found as two separate cases) lets ONE single binary search loop handle BOTH outcomes uniformly - no special-casing needed for whether the target actually exists in the array.

1. Binary search for the SMALLEST index pos such that arr[pos] >= target. 2. That index is the answer whether the target is actually present (an exact match) or not (the correct insertion point). 3. Let the search range's upper bound start at n (one position past the last valid index), so the answer can legally be 'insert at the very end'.

Time: O(log n) - a standard binary search. Space: O(1) - just a few pointer variables.

target may be smaller than every element (answer 0) or larger than every element (answer n); n may be 1.

Be ready to explain why unifying the 'found' and 'not found' cases into one 'first position >= target' search is more elegant than writing separate logic for each - a small framing choice that simplifies the whole solution.