Solve Search Insert Position Using Binary Search
Company: Amazon
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Scenario
Live coding round for an Amazon Applied Scientist position; candidate must solve LeetCode 35 (Search Insert Position) without helper libraries.
##### Question
Given a sorted array of distinct integers nums and an integer target, return the index if target exists; otherwise return the index where it would be inserted to keep order. Implement the solution using an explicit binary search (no built-in bisect).
##### Hints
Iterative or recursive binary search, O(log n) time, manage low/high pointers and insertion position when loop exits.
Overview: This question evaluates proficiency in binary search, algorithmic implementation on sorted arrays, and understanding of time complexity and index management.
Given a sorted array of distinct integers nums and an integer target, return the index of target if it is present. Otherwise, return the index where target should be inserted to maintain ascending order. Implement the solution using an explicit binary search (do not use built-in bisect).
Constraints
- 0 <= len(nums) <= 100000
- nums is sorted in strictly increasing order
- All elements in nums are distinct
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
- Expected time complexity: O(log n)
- Do not use built-in bisect functions
Hints
- Maintain two pointers low and high bounding the current search range.
- Compute mid = (low + high) // 2 and compare nums[mid] with target.
- When the loop ends, low will be the correct insertion index.