二進制搜索，計數複製

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並利用它。我可以寫出整個解決方案，但你自己來解決它會更好。