黑马程序员技术交流社区
标题:
折半查找的min怎么看？
[打印本页]
作者:
不想飞不到
时间:
2014-8-21 11:15
标题:
折半查找的min怎么看？
public static int halfSearch2(List<String> list,String key,Comparator<String> cmp)//添加了比较器参数，使方法具备比较性（对象元素可能本来没有比较性）
{
int max,min,mid;
max = list.size()-1;
min = 0;
while(min<=max)
{
mid = (max+min)>>1;// /2;
String str = list.get(mid);
int num = cmp.compare(str,key);//比较器，扩展了二分查找的比较范围
if(num>0)
max = mid -1;
else if(num<0)
min = mid + 1;
else
return mid;
}
return -min-1;
}
class StrLenComparator implements Comparator<String>
{
public int compare(String s1,String s2)
{
if(s1.length()>s2.length())
return 1;
if(s1.length()<s2.length())
return -1;
return s1.compareTo(s2);
}
}
老毕的折半查
如果搜索键包含在列表中，则返回搜索键的索引；否则返回 (-(
插入点
) - 1)。
插入点
被定义为将键插入列表的那一点：即第一个大于此键的元素索引；如果列表中的所有元素都小于指定的键，则为list.size()。注意，这保证了当且仅当此键被找到时，返回的值将 >= 0。
为什插入点等于min？
作者:
刘瑞
时间:
2014-8-21 11:15
看一下插入排序的原理就知道了。插入点位于min和max之间，如果min大于或等于了max，则表示所有元素都折半了，仍未找到和搜索键相同的值。此时min的位置就是插入点位置。
作者:
不想飞不到
时间:
2014-8-21 12:20
突然灵光一闪，哈哈哈
作者:
MVP
时间:
2014-8-21 12:59
二分查找的原理就是在一个已经排好序的集合或者数组中，获取中间的元素的跟要查找的元素进行对比。如果min>max的时候，就代表该元素都找不到，但是可以确认的是，这个值一定大于min，所以这个插入点等于min的位置。
作者:
静水流深2014
时间:
2014-8-21 18:49
min就是查找范围的最小边界，折半查找的核心就是不断的缩短边界，如果大于min则向着增大的方向来缩短边界，否则向着减小的方向来缩短边界。核心思想，减小查找的范围，需要注意的是折半查找必须是排过序的才可以。
作者:
逍遥客
时间:
2014-8-22 08:10
额，不错啊
作者:
inception
时间:
2014-8-23 20:06
看看。。。
作者:
奋发吧小白
时间:
2014-8-25 00:23
建议再仔细看下视频 个人感觉 没有其他人可以比毕老师讲解的更清楚了！加上画图！很容易理解的！
作者:
sxyglx2010
时间:
2014-9-6 18:28
顶一个，感觉楼上回答的不错
作者:
fouraa
时间:
2014-9-8 10:35
继续学习~
作者:
980344791
时间:
2014-10-10 20:03
我也是，老毕的视频看3遍就很牛逼了，这些问题都会了。。。
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2