Постановка задачи

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

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

Постановка задачи взята с: https://leetcode.com/problems/search-insert-position

Пример 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

Пример 4:

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

Пример 5:

Input: nums = [1], target = 0
Output: 0

Ограничения:

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

Объяснение

Подход грубой силы

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

Решение легко и быстро реализовать, но оно занимает O(n) время.

Поскольку элементы отсортированы, мы можем использовать алгоритм двоичного поиска, чтобы найти правильный индекс.

Бинарный подход к поиску

Алгоритм

- set start = 0 and end = N - 1.
- loop while (start <= end)
  - mid = (start + end)/2

  - if target > nums[mid]
    - start = mid + 1
  - else if target < nums[mid]
    - end = mid - 1
  - else
    - return mid

- return start

Решение C++

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int start = 0;
        int end = nums.size()-1;

        while(start <= end){
            int mid = (start + end)/2;

            if(target > nums[mid]){
                start = mid + 1;
            }else if(target < nums[mid]){
                end = mid - 1;
            }else{
                return mid;
            }
        }

        return start;
    }
};

Решение Golang

func searchInsert(nums []int, target int) int {
    start := 0
    end := len(nums) - 1

    for start <= end {
        mid := (start + end) / 2

        if target < nums[mid] {
            end = mid - 1
        } else if target > nums[mid] {
            start = mid + 1
        } else {
            return mid
        }
    }

    return start
}

Решение для JavaScript

var searchInsert = function(nums, target) {
    let start = 0, end = nums.length - 1;
    let mid;

    while( start < end ){
        mid = (start + end) / 2;

        if( target < nums[mid] ){
            end = mid - 1;
        } else if( target > nums[mid] ){
            start = mid + 1;
        } else {
            return mid;
        }
    }

    return start;
};

Давайте запустим наш алгоритм в пробном режиме, чтобы увидеть, как работает решение.

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

Step 1: start = 0
        end = nums.size() - 1
            = 4 - 1
            = 3

Step 2: loop while( start < end )
        0 < 3
        true

        mid = (start + end)/2
            = (0 + 3)/2
            = 3/2
            = 1

        if target < nums[mid]
           5 < nums[1]
           5 < 3
           false
        else if target > nums[mid]
           5 > nums[1]
           5 > 3
           true

           start = mid + 1
                 = 1 + 1
                 = 2

Step 3: loop while( start < end )
        2 < 3
        true

        mid = (start + end)/2
            = (2 + 3)/2
            = 5/2
            = 2

        if target < nums[mid]
           5 < 5
           false
        else if target > nums[mid]
           5 > nums[1]
           5 > 5
           false
        else
          return mid
          return 2

So the answer returned is 2.

Первоначально опубликовано на https://alkeshghorpade.me.