这个具有二分查找和 while 循环的算法的时间复杂度是多少？

Question

我试图找出 findingDup 算法的运行时间复杂度，因为我不确定它是 O(n) 还是 O(log n ).我的目标是实现一个次线性算法，找出 int 值 被重复的次数。您可以假设给定的数组 int[] A 总是排序的。如果您有任何其他问题，请在下方留言。

public class Controller {
    
    public static void main(String[] args){
        
        int[] A = {-1, 2, 3, 5, 6, 6, 6, 9, 10};
        
        int value = 6;
        
        System.out.println(findingDup(A, value));
        
    }// end main
    
    public static int findingDup(int[] a, int x){
        
        int counter = 0;
        
        int index = binarySearch(a, x); // index = 4 
        
        int leftIndex = index - 1;      // leftIndex = 3
        int rightIndex = index + 1;     // rightIndex = 5
        
        if(index == -1){
            return 0;
        }
        else if(a[index] == x){
            counter++;
        }
        
        // checking if all numbers are dups
        if(a[0] == a[a.length - 1]){
            return a.length;
        }
        
        if(leftIndex >= 0){
            
            while(a[leftIndex] == x){
                counter++;
                leftIndex--;
                
                if(leftIndex < 0){
                    break;
                }
                
            }
            
        }
        
        if(rightIndex <= a.length - 1){
           
            while(a[rightIndex] == x){
                counter++;
                rightIndex++;
                
                if(rightIndex > a.length - 1){
                    break;
                }
                
            }
            
        }
        
        return counter;
        
    }// end method
    
    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;
    
    }// End Method
    
    
}// end class

Answer 1

您的代码是 O(k + log n)，其中“k”是该值出现在列表中的次数。

如果 k = O(n) 它会退化为 O(n)。

例如，在列表为 [6, 6, 6, 6, 6, ...] 的极端情况下，您将最终处理所有元素。

您仍然可以通过运行多次二分查找来解决这个问题。

首先你运行它找到第一次出现的“值”，然后你运行它再次找到第一个大于值的数字（搜索值+1）。

您的二进制搜索算法需要修改为 return 值的第一次出现，或者如果找不到该值则使用更大的值。

截至目前，它会发现任何事件，但不能保证是第一个或最后一个。

您的二分查找条件如下：

if (smaller) {...}
else if (larger) {...}
else {we have found it!}

所以它可以 return 任何事件。

您应该寻找一个索引：

a[mid - 1] < value && a[mid] >= value

mid-1 可以小于 0，因此您需要先检查它。

如果不是这种情况，我们还没有找到第一个出现的地方，需要向左或向右移动索引。

这个具有二分查找和 while 循环的算法的时间复杂度是多少？

What is the time complexity of this algorithm that has binary search along with while loops?

java

algorithm

time-complexity