Problem Description
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.
Key Insights
- The array is sorted and contains distinct integers.
- The problem can be solved using binary search, which efficiently narrows down the possible positions for the target value.
- If the target is found, return its index; otherwise, return the index where the target should be inserted to maintain sorted order.
Space and Time Complexity
Time Complexity: O(log n)
Space Complexity: O(1)
Solution
To solve this problem, we utilize the binary search algorithm. The algorithm works by maintaining two pointers (left and right) that represent the current search range. We repeatedly calculate the midpoint of the current range and compare the value at that midpoint to the target. If the target is less than the midpoint value, we move the right pointer to mid - 1; if it is greater, we move the left pointer to mid + 1. This process continues until we either find the target or determine the appropriate insertion index.