使用二进制搜索在排序列表中查找重复项的 while 循环的时间复杂度是多少？

Question

我想知道函数 duplicate 的时间复杂度是多少，因为我认为它是 O(nlogn) 由于使用二进制搜索算法，同时实现一个 while 循环来搜索数组中第一个实例位置的左侧和右侧，其中找到值以查看它是否在排序数组中重复。我想知道它是否 O(logn) 因为我在想 while 循环实际上并没有遍历所有元素，只是我们正在搜索的值附近的元素，看看是否它重复了。如果不是，我将不胜感激使它成为 O(logn) 的任何建议。

public class Problem2 {

    public static void main(String[] args) {
        
        int[] arrayA = {-1, 2, 3, 5, 6, 6, 6, 9, 10};
        
        int repeatedValue = 6;
        
        System.out.println(duplicates(arrayA, repeatedValue));
    }
    
    public static int duplicates(int[] a, int x){
        
        int counter = 0;                 //counter for duplicates.
        int index = binarySearch(a, x);  // index = 4 where x is.
        int leftIndex = index - 1;       // leftIndex = 3
        int rightIndex = index + 1;      // rightIndex = 5
        
        //Condition incase value does not exist.
        if(index == -1)
            return -1;
        
        //While loop to check left and right side of index for duplicates.
        while(a[leftIndex] == x || a[rightIndex] == x){
            
            if(a[leftIndex] == x){
                counter++;
                leftIndex--;
                
            }
            else if(a[rightIndex] == x){
                counter++;
                rightIndex++;
                
            }
           
        }
        
        //returning the counter plus one because we did not count the first instance
        //when it was searched.
        return counter + 1;
    }
    
    public static int binarySearch(int[] a, int x){
        
        int low = 0, high = a.length - 1;
        
        while(low <= high){
            
            int mid = (low + high) / 2;
            
            if(a[mid] < x)
                low = mid + 1;
            else if(a[mid] > x)
                high = mid - 1;
            else
                return mid;
        }
        return -1;
    }
}

Answer 1

不是 O(n*logn)，因为您不是进行线性搜索 FOR 每个二进制搜索：您正在做线性搜索 AND 二分搜索。

我是 O(logn) 或 O(n)，具体取决于您的目标数字有多少重复项。由于 O(n) 大于 O(logn)，您的最坏情况复杂度为 O(n).

要进一步说明您的平均案例复杂度，我们需要知道平均案例输入是什么样的。

如果大小为 n 的列表（您实际搜索的）的平均重复项数低于 logn，则平均案例复杂度为 O(logn) .

关于如何制作的建议O(logn):

要进行二分查找，您已经对输入进行了预计算步骤，即对数组进行排序。

更改预计算步骤，不仅对数组进行排序，还对数组进行去重，并将每个唯一数字的重复数存储在单独的数组中。

那么搜索算法就变成了：

二进制搜索你的目标数字的正确索引
Return 具有重复计数的单独数组中数字的重复次数，使用您在步骤 1 中找到的索引

只有当您在同一输入数据上搜索大量不同的目标数字时，这才有意义。

使用二进制搜索在排序列表中查找重复项的 while 循环的时间复杂度是多少？

What would be the time complexity for a while loop that uses binary search for finding duplicates in a sorted list?

java

algorithm

data-structures

time-complexity

complexity-theory