二进制搜索，计数复制

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）打印（顶部索引 - 底部索引）将给我在数组中的目标编号的时间。

我的代码是否是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, index，另一个寻找index, size两个序列中的数字都是找到的数字。

所以我建议你只要通过索引findTopIndex和findBottomIndex并利用它。我可以写出整个解决方案，但你自己来解决它会更好。