Поиск Вставить Положение Хороший Подход

Question

Я делал эту проблему на Leetcode и создал это решение для него в java, и оно было успешно отправлено.

class Solution {
    public int searchInsert(int[] nums, int val) {
     for(int i=0;i<nums.length;i++){
         if(nums[i]!=val){
             if(nums[i]>val){
                 return i;
             }
         }
         if(nums[i]==val)
             return i;
         if(i==nums.length-1 && nums[i]!=val)
             return i+1;       

         }
      return 0;  
    }   
}

И когда я проверил это решение через Google, я нашел бинарный поиск решение, которое это

class Test 
{ 
    // Simple binary search algorithm 
    static int binarySearch(int arr[], int l, int r, int x) 
    { 
        if (r>=l) 
        { 
            int mid = l + (r - l)/2; 
            if (arr[mid] == x) 
                return mid; 
            if (arr[mid] > x) 
                return binarySearch(arr, l, mid-1, x); 
            return binarySearch`enter code here`(arr, mid+1, r, x); 
        } 
        return -1; 
    } 

Я хочу спросить: мой подход плох, чем приведенный ниже метод двоичного поиска?

Answer 1

Бинарный поиск - лучшее решение для поиска точки вставки. Ваше решение найдет индекс вставки в O(n) и бинарный поиск в O(log(n)).

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

Разница в сложности заключается в том, что ваше решение уменьшит ширину пространства поиска на 1 в каждой l oop итерации => линейной сложности. С другой стороны, двоичный поиск сокращает пространство поиска пополам при каждом рекурсивном вызове => logarithmi c сложность.