Search Insert Position

EasyBinary Searchbinary search

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a sorted array of distinct integers nums (sorted in strictly increasing order) and an integer target. Return the index of target if it is present in nums. If target is not in the array, return the index where it would be inserted so that the array remains sorted. Your solution must run in O(log n) time.

Examples

Input: nums = [1, 3, 5, 6], target = 5
Output: 2
The value 5 is found at index 2.
Input: nums = [1, 3, 5, 6], target = 2
Output: 1
2 is not present. It would fit between 1 (index 0) and 3 (index 1), so it should be inserted at index 1.
Input: nums = [1, 3, 5, 6], target = 7
Output: 4
7 is larger than every element, so it would be appended at the end, at index 4.

Constraints

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

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More binary search problems