二分搜索法排序

狼王

本帖最后由殷婷婷于 2013-11-15 12:11 编辑

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class Test {
public static void main(String[] args) {
// TODO Auto-generated method stub
List<String> list = new ArrayList<String>();
list.add("java");
list.add("demo");
list.add("yinyi");
list.add("zo");
list.add("demo");
Collections.sort(list,new StrLenComparator1());
System.out.println(list);
System.out.println(halfSearch2(list,"zo",new StrLenComparator1()));
}
public static int halfSearch2(List<String> list,String key,Comparator<String> cmp)
{
int min,max,mid;
max = list.size()-1;
min = 0;
while(min<=max)
{
mid = (min+max)>>1;
String str = list.get(mid);
int num = cmp.compare(str,key);
if(num>0)
max = mid - 1;
if(num<0)
min = mid + 1;
else return mid;
}
return -min-1;
}
}
class StrLenComparator1 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);
}
}

复制代码

按照二分搜索法排序，System.out.println(halfSearch2(list,"zo",new StrLenComparator1()));的结果应该是0，可是运行了下，输出是2，实在找不出哪里错了，用binarySearch(list,"zo",new StrLenComparator()))输出的是正确的，肯定是程序哪儿写错了，麻烦帮我看一下，到底是哪儿的错。

linjl_ll · linjl_ll

我们来分析下下面的代码，第一次执行循环时如下
while(min<=max)
            {
                     mid = (min+max)>>1;//mid =2
                     String str = list.get(mid);//str的值为"demo"
                     int num = cmp.compare(str,key);//返回值大于0即num>0
                     if(num>0)//这个if语句会执行num>0
                              max = mid - 1;//max=1
                     if(num<0)//这个if不会执行，所以他后面的else会执行
                              min = mid + 1;
                     else return mid;//返回mid即2
            }

你的第二个if语句应该是else if。

lichao · lichao

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class Test {
public static void main(String[] args) {
// TODO Auto-generated method stub
List<String> list = new ArrayList<String>();
list.add("java");
list.add("demo");
list.add("yinyi");
list.add("zo");
list.add("demo");
Collections.sort(list,new StrLenComparator1());
System.out.println(list);
System.out.println(halfSearch2(list,"zo",new StrLenComparator1()));
}
public static int halfSearch2(List<String> list,String key,Comparator<String> cmp)
{
int min,max,mid;
max = list.size()-1;
min = 0;
while(min<=max)
{
mid = (min+max)>>1;
String str = list.get(mid);
int num = cmp.compare(str,key);
if(num>0)
max = mid - 1;
else if(num<0) //少写了一个else //如果比较值是大于0的数，在上面的if比较后，又在此if比较，由于num大于0，所以执行else 程序结束输出返回值2；
min = mid + 1;
else return mid;
}
return -min-1;
}
}
class StrLenComparator1 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);
}
}

复制代码

殷婷婷 · 殷婷婷

linjl_ll 发表于 2013-11-15 11:03
我们来分析下下面的代码，第一次执行循环时如下
while(min>1;//mid =2
String str ...

是的哦，谢谢啦，哈哈:victory:

殷婷婷 · 殷婷婷

lichao 发表于 2013-11-15 11:42

谢谢帮助啊:victory:

帐号		自动登录	找回密码
密码			加入黑马

二分搜索法排序

评分

4 个回复