Описание испытания

Учитывая отсортированный массив различных целых чисел и целевое значение, вернуть индекс, если цель найдена. Если нет, верните индекс туда, где он был бы, если бы он был вставлен по порядку.

Вы должны написать алгоритм со сложностью выполнения O(log n).

Пример 1:

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

Пример 2:

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

Пример 3:

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

Подход

  • binary seaerch подход к этому вопросу чертовски прост, а также легко думать об этом.
  • массив отсортирован, поэтому нам просто нужно выяснить, где его разместить.
  • поэтому нам просто нужно выяснить позицию, в которой previous value меньше нашего элемента, а значение next больше, чем наш элемент.
  • Вот как выяснилось, что это проблема бинарного поиска.

Сложность

  • Временная сложность: O (log (n))
  • Сложность пространства: O(1)
function searchInsert(nums: number[], target: number): number {
  let low = 0;
  let high = nums.length - 1;
  let mid;

  if (target > nums[high]) {
    return high + 1;
  }

  while (low <= high) {
    mid = Math.floor((low + high) / 2);

    if (nums[mid] === target) {
      return mid;
    }

    if (target < nums[mid]) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }

  return low;
}