🎉 Yay! DSA-30 is now live!
Day 13 - Searching Algorithms
Practice Questions
Search Insert Position

Search Insert Position

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.

Constraints

  • 1 <= n <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums contains distinct values sorted in ascending order.
  • -10^4 <= target <= 10^4

Test Cases

  • Input: nums = [1, 3, 5, 6], target = 5
    Output: 2

  • Input: nums = [1, 3, 5, 6], target = 2
    Output: 1

  • Input: nums = [1, 3, 5, 6], target = 7
    Output: 4

Code

Approach 1: Binary Search

Explanation

  1. Initialize left to 0 and right to nums.size() - 1.
  2. Use a while loop to perform binary search.
  3. Calculate the middle index mid using left + (right - left) / 2.
  4. If nums[mid] is equal to target, return mid.
  5. If nums[mid] is less than target, update left to mid + 1.
  6. Otherwise, update right to mid - 1.
  7. If the loop exits without finding the target, return left.

Analysis

  • Time Complexity: O(log n)
  • Space Complexity: O(1)
Approach 2: Linear Search

Explanation

  1. Iterate through the array using a for loop.
  2. If the current element is greater than or equal to the target, return the current index.
  3. If the loop completes without finding a suitable position, return the length of the array.

Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(1)
Problem ListSearch in Rotated Sorted Array