在有序数组中搜索 K 的首次出现

Question

我正在尝试解决 Java 中编程面试要素 (EPI) 中的问题 11.1：在排序数组中搜索 K 的首次出现。

书中的问题描述：

Write a method that takes a sorted array and a key and returns the index of the first occurrence of that key in the array.

他们在书中提供的解决方案是一种改进的二进制搜索算法，该算法在 O(logn) 时间内运行s。我也基于修改后的二进制搜索算法编写了自己的算法，但略有不同——它使用递归。问题是我不知道如何确定我的算法的时间复杂度——我最好的猜测是它会在 O(logn) 时间内运行因为每次调用函数都会减少候选的大小值减半。我已经根据 EPI Judge 提供的 314 个 EPI 测试用例测试了我的算法，所以我知道它有效，我只是不知道时间复杂度 - 这是代码：

public static int searchFirstOfKUtility(List<Integer> A, int k, int Lower, int Upper, Integer Index)
{
    while(Lower<=Upper){

      int M = Lower + (Upper-Lower)/2;

      if(A.get(M)<k)
        Lower = M+1;

      else if(A.get(M) == k){
        Index = M;
        if(Lower!=Upper)
          Index = searchFirstOfKUtility(A, k, Lower, M-1, Index);
        return Index;
      }

      else
        Upper=M-1;
    }

    return Index;
}

下面是测试用例调用来执行我的功能的代码：

public static int searchFirstOfK(List<Integer> A, int k) {
    Integer foundKey = -1;
    return searchFirstOfKUtility(A, k, 0, A.size()-1, foundKey);
  }

所以，谁能告诉我我的算法的时间复杂度是多少？

Answer 1

假设传递参数是 O(1) 而不是 O(n)，性能是 O(log(n)).

分析递归的常用理论方法是调用Master Theorem。也就是说如果一个递归算法的性能遵循一个关系：

T(n) = a T(n/b) + f(n)

那么有3个案例。在简单的英语中，它们对应于：

性能由递归底部的所有调用决定，因此与调用的数量成正比。
每个递归级别之间的性能是相等的，因此与有多少递归级别乘以任何递归层的成本成正比。
性能主要取决于第一次调用时完成的工作，因此与 f(n) 成正比。

您属于情况 2。每个递归调用的成本相同，因此性能取决于 O(log(n)) 个递归级别乘以每个级别的成本这一事实。假设传递固定数量的参数是 O(1)，那确实是 O(log(n)).

请注意，此假设对于 Java 是正确的，因为您在传递数组之前没有制作数组的完整副本。但重要的是要意识到并非所有语言都如此。例如，我最近在 PL/pgSQL 中做了很多工作，其中数组是按值传递的。这意味着您的算法应该是 O(n log(n)).

在有序数组中搜索 K 的首次出现

Search a Sorted Array for First Occurrence of K

algorithm

search

binary-search

time-complexity

sortedlist