搜索插入位置良好方法

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 =>线性复杂度。另一方面，二进制搜索将在每次递归调用时将搜索空间减少一半=>对数复杂度。