java - 二分查找，计算重复项

Question

我已经排序数组

{1,2,3,5,5,5,7,8,8}

我想计算我发送的数字在 longn 数组中出现的次数。

例如:

public static int count(int[] array,5)

将回复3

public static int count(int[] array,8)

将回复2

所以我的计划是:

1) 进行二分查找来查找数字

2)二分查找顶部边框索引和底部边框索引。

3)print(顶部索引 - 底部索引)将给出数组中目标数字的时间。

我的代码是logn吗？ 请帮忙! :)

    public class binarySearch
{
    public static void main(String[]args)
    {
        System.out.println("d");
        int[]data={1,1,2,3,1,1,1};
        System.out.println(count(data,1));
    }

    public static int count(int[] a, int x)
    {
        int low=0;
        int high = a.length-1;
        int count=0;

        while(low <=high)
        {
            int mid=((low+high)/2);         
            if(x>a[mid])
                low=mid+1;
            if(x<a[mid])
                high=mid-1;

            if(x==a[mid])            
            {
                int top=findTopIndex(a,x,mid);                
                int bottom=findBottomIndex(a,x,mid);
                return (top-bottom);

            }

        }    
        return 111111111;

    }

    public static int findTopIndex(int[] a, int x, int index)
    {
        int low=index;
        int high = a.length-1;    
        int mid;
        if(x==a[high])
        return high;

        while(low <= high)
        {            
           mid=((low+high)/2);         
           if(x<a[mid]&&x==a[mid-1])
           return mid-1;
           else if(x==a[mid])
                low=mid+1;
           else if(a[mid]>x && a[mid-1]!=x)
           high=mid-1;


        } 
        return 11111111;

    }
    public static int findBottomIndex(int[] a, int x, int index)
    {
        int low=0;
        int high = index-1;    
        int mid;
        if(x==a[low])
        return low-1;

        while(low <= high)
        {            
         mid=((low+high)/2);         
           if(x>a[mid]&&x==a[mid+1])
           return mid;
           else if(x==a[mid])
                high=mid-1;
           else if(a[mid]<x && a[mid+1]!=x)
           low=mid+1;

        } 
        return 111;

    }

}

Answer 1

您所写的内容非常接近您需要的解决方案。首先进行二分搜索来查找您要搜索的数字的单个实例(假设它在位置 index 上找到)，然后再进行两次二分搜索 - 一个针对序列 0，索引，以及索引，大小 1，用于查找两个序列中找到的数字的位置。

因此，我建议您只需将索引传递给 findTopIndex 和 findBottomIndex 并使用它。我可以写出整个解决方案，但你最好自己来解决。