我已经排序了数组
{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 (top index - bottom index) 会给我数组中目标数字的时间。
我的代码是 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;
}
}