DevExCode

35. Search Insert Position

ArrayBinary Search

Explanation:

To solve this problem with a runtime complexity of O(log n), we can use a modified binary search algorithm. The idea is to find the target value in the sorted array. If found, return the index. If not found, return the index where it would be inserted while maintaining the sorted order.

  1. Initialize two pointers, low and high, to the start and end of the array respectively.
  2. While low <= high, calculate the middle index mid.
  3. If the target is equal to the value at index mid, return mid.
  4. If the target is less than the value at index mid, update high = mid - 1.
  5. If the target is greater than the value at index mid, update low = mid + 1.
  6. After the loop, return the low pointer as the position to insert the target.

Time Complexity: O(log n) Space Complexity: O(1)

:

View Leetcode Problem
class Solution {
    public int searchInsert(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

  • Add import statement if required.
  • Optimize the code for better time or space complexity.
  • Add test cases to validate edge cases and common scenarios.
  • Handle error conditions or invalid inputs gracefully.
  • Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Previous QuestionNext Question