本帖最后由 贺靖轩 于 2013-4-1 11:23 编辑
黑马程序员_毕向东_Java基础视频教程第04天-07-数组(折半查找).avi
毕老爷这节视频给大家讲了折半查找 提到了折半查找的二种实现方式
还进到使用此方式的前提：有序
但是忽略了另一个方面：无重
代码：
public class SearchTest
{
public static void main(String[] args)
{
int[] arr=new int[]{1,2,2,2,2,2,3};
int index=getIndex(arr,2);
System.out.println(index);
}
public static int halfSearch(int[] arr,int key)
{
int min,max,mid;
min=0;
max=arr.length-1;
mid=(max+min)>>1;
while(key!=arr[mid])
{
if(key>arr[mid])
{
min=mid+1;
}
else if(key<arr[mid])
{
max=mid-1;
}
if(min>max)
{
return -1;
}
mid=(max+min)>>1;
}
return mid;
}
public static int halfSearch_2(int[] arr,int key)
{
int min,max,mid;
min=0;
max=arr.length-1;
mid=(max+min)>>1;
while(min<=max)
{
mid=(max+min)>>1;
if(key>arr[mid])
{
min=mid+1;
}
else if(key<arr[mid])
{
max=mid-1;
}
else
{
return mid;
}
}
return -1;
}
public static int getIndex(int[] arr,int key)
{
int min,max,mid;
min=0;
max=arr.length-1;
mid=(max+min)>>1;
while(min<=max)
{
mid=(max+min)>>1;
if(key>arr[mid])
{
min=mid+1;
}
else if(key<arr[mid])
{
max=mid-1;
}
else
{
return mid;
}
}
return min;
}
}
结果：
2 //为查找元素的下标
如果数组中有重复元素，虽然找到了该元素的下标（位于中间的元素) 但却忽略了数组中该元素的个数。
如果数组中只有一个重复元素：
一个省事的方法就是：
借助 TreeSet 可以计算出该元素的个数 至于其位置 可以通过相应推理获得。
Set<Integer> set=new TreeSet<Integer>();
for(int i:arr)
{
set.add(i);
}
System.Out.Println(set.size());
int numOfKey=set.size()-arr.size();
如果存在多个元素，恩，重复的，大家想办法吧。
我脸皮厚，说我抠的随便喷，哈哈。
|
收藏
淘帖
踩
