搜索插入位置好方法

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)) 中找到二进制搜索。

对于上下文：这种算法的时间复杂度是根据算法必须执行的比较次数来衡量的。

复杂性的差异是因为您的解决方案会在每次循环迭代中将搜索宽度 space 减少 1 => 线性复杂性。 另一方面，二分搜索将在每次递归调用时将搜索 space 减半 => 对数复杂度。