这是老师讲折半查找的模拟binarySearch的一个函数，
public static int halfSearch(List<String> list,String key)
        {
                int max,min,mid;
                max=list.size()-1;
                min=0;
                while(min<=max)
                {
                        mid=(max+min)>>1;
                        String str=list.get(mid);
                int num=str.compareTo(key);
                if(num>0)
                        max=mid-1;
                else if(num<0)
                        min=min+1;
                else
                        return mid;
                       
                }
                return -min-1;
        }
最后的return -min-1;说是返回的插入点减1;可写得程序明显不是 负的插入点减1嘛？
还有就是最后的min值为什么是插入点，我没反应过来。

天道酬勤 发表于 2012-5-1 00:17
嗯 ，怎么没技术分啊 ，郁闷.......

老师没上线呢吧，你不是实名，好像没技术分的。 会给你论坛金钱~

嗯 ，怎么没技术分啊 ，郁闷.......

天道酬勤 发表于 2012-4-30 22:56
//如果你要查找的在这个数组的最左边，返回的应该是个0-1=-1；但是右边呢？就是4-1=3；
//这样不是说明了在 ...

明白了，为了在插入点在最左边时不返回0，所以需要-1，对吧
谢谢你哦~

     折半查找首先要保证元素有序的，给我一个数如果在数组中查找不到，因为min是数组的0角标，那就min-1返回的就是-1，表示这个数没有在我这个数组中，找不到这个数返回值可以自己定义，你不用min-1，直接返回-1，也行，也可以代表这个数没有在此数组中。还有可以抛出一个RuntimeException异常。

//如果你要查找的在这个数组的最左边，返回的应该是个0-1=-1；但是右边呢？就是4-1=3；
//这样不是说明了在数组中存在吗？所以用-min表示这个数在数组不存在,-min-1=-4-1=-5;
//这样我们就知道了要查找的数应该插入4的后面，这样加以区分的.o了。

天道酬勤 发表于 2012-4-30 22:16
//例如一个数组[1,3,5,7,9]
//你要查找4插入的位置你该怎么做，第一次在数组中查找，发现应该做在0和2的位 ...

第一次是max=4，min=0，mid=2；比较后，max=mid-1=1；min=0；mid=0；再比较后 min=mid+1=1，max=1；mid=1；再比较，min=mid+1=2；max=1；循环退出。min=2；有点懂了。但为什么是return -min-1啊

//例如一个数组[1,3,5,7,9]
//你要查找4插入的位置你该怎么做，第一次在数组中查找，发现应该做在0和2的位置里面
//这个是时候min是0，max是2，mid是1，第二次比较，发现在1和2之间
//再次折中min是1，max是2，mid是（1+2）/2=1，发现在比3大，
//再次折中，min是2，max是2，mid是（2+2）/2=2,发现比5小
//再次折中，min是2，max是1，while条件不成立，
//以此分析，你觉的你要插入的数放在那个地方，肯定是最后一次循环条件不成立是min的位置上，就是2的位置上
//因为比较的那个数比min大，所以再次折中，发现条件不成立才停止循环。
//如果你插入的是0，依次类推，折中，再次折中，发现0比中间值1还小。再次循环，条件不成立
//所以应该将数字插入min的位置上 ，就是2的位置上，因为0代表数组的第一个元素，所以将减min-1；