黑马程序员技术交流社区

标题: 关于二分查找法的问题 [打印本页]
作者: 杨银川    时间: 2011-12-3 21:31
标题: 关于二分查找法的问题
本帖最后由 杨银川 于 2011-12-4 12:22 编辑

public class BinarySearch {
//二分查找
public static int halfsearch_1(int[] arr,int key){
        int min,max,mid;
        min=0;
        max=arr.length-1;
        while(min<max){
                mid=(min+max)/2;
                if(arr[mid]<key){
                        min=mid+1;
                }else if(arr[mid]>key){
                        max=mid-1;
                }else{
                return mid;
                }
        }
        return -1;
}
//查找插入数组中的数(不存在)的位置  
public static int halfsearch_2(int[] arr,int key){
        int min,max,mid=0;
        min=0;
        max=arr.length-1;
        while(min<max){
                mid=(min+max)/2;
                if(arr[mid]<key){
                        min=mid+1;
                }else if(arr[mid]>key){
                        max=mid-1;
                }else{
                return mid;
                }
        }
        return min;
}
public static int halfsearch(int[] arr,int key){
        for(int i=0;i<arr.length;i++){
                if(arr==key){
                        return halfsearch_1(arr, key);
                }else{
                        return halfsearch_2(arr, key);
                }
        }
        return -1;
}
public static void main(String[] args){
        int [] arr={1,3,5,7,8,12,45,89};
        int index=halfsearch(arr,6);
        System.out.println(index);
}
}

我的疑问是：运行结果是2，差一位。是不是二分法和数组的奇偶性有关啊？如果没有，该怎么优化一下才好呢？
作者: 颜秉武    时间: 2011-12-3 22:36
楼主这个代码繁琐了点,我看的很蛋疼,但是没找到,楼主想要的不就是给定数字插入给定数组,应该插入的索引么?不需要二分法吧?不知道我看懂没,今天头很疼,状态极差,
就按自己的感觉,改一下吧!弄错了,楼主可别骂我捣乱!呵呵
  1. public class Halfsearch {
  2.         public static void main(String[] args) {
  3.                 // TODO Auto-generated method stub
  4.                 int[] arr = { 1, 3, 5, 7, 8, 12, 45, 89 };
  5.                 int index = halfsearch(arr, 15);
  6.                 System.out.println("应插入的索引位置是"+index);
  7.         }

  9.         public static int halfsearch(int[] arr, int key) {
  10.                 for (int i = 0; i < arr.length; i++) {
  11.                         if (arr[i] > key) {
  12.                                 return i;
  13.                         }
  14.                 }
  15.                 return arr.length;
  16.         }
  17. }
复制代码
作者: 赵燕燕    时间: 2011-12-3 22:43
while(min<max)这里错了，min=max时也要查找一次的。
而且，你这样写太麻烦了。while(min<=max)就可以实现循环去查找，为什么还要先在halfsearch(int[] arr,int key)中 for循环一下。可以这样写：
public class BinarySearch
{
        //二分查找
        public static int halfSearch_1(int[] arr,int key)
        {
                int min,max,mid;
                min=0;
                max=arr.length-1;
                while(min<=max){
                        mid=(min+max)/2;
                        if(arr[mid]<key){
                                min=mid+1;
                        }else if(arr[mid]>key){
                                max=mid-1;
                        }else{
                        return mid;
                        }
                }
                return -1;
        }
        public static void main(String[] args)
        {
                int [] arr={1,3,5,7,8,12,45,89};
                int index=halfSearch_1(arr,6);
                System.out.println(index);
        }
}
作者: 黄喆    时间: 2011-12-4 00:16
本帖最后由 黄喆 于 2011-12-6 14:21 编辑

你查找插入数组中的数(不存在)的位置，返回的只是的是原数组中和key最相近的一个数即mid的位置，如果key大于原数组中的值，则应返回mid+1;反之返回mid
作者: 杨银川    时间: 2011-12-4 10:18
赵燕燕 发表于 2011-12-3 22:43
while(min

感谢你的回答，你给的代码我运行了，是-1，也就是说没有查到，可我想的是我想实现两种功能，如果查到则返回位置下标，如果没有查到，则返回这个数在数组中的插入位置。
作者: 杨银川    时间: 2011-12-4 10:38
永无止境的、 发表于 2011-12-3 22:36
楼主这个代码繁琐了点,我看的很蛋疼,但是没找到,楼主想要的不就是给定数字插入给定数组,应该插入的索引么? ...

哦，可能是我没有表示清楚，呵呵，其实我想的是针对main方法中的同一个数组，我建立两个方法，一个用二分法来实现查找数组中存在的数，如果没有，就用另外一个查找这个不存在的数应该插入到哪个位置，我试了几回，有时数组中的数目的奇偶性会对结果产生不同，不过你给的方法克服了这一点，我运行了一下你给的代码，查找不存在的数，比方说6，那返回的是3，但是要是我想查个存在的，比如8，那么返回的是5，应该是4就对了，所以你看该怎么实现啊，谢谢了
作者: 颜秉武    时间: 2011-12-4 10:42
楼主,你如果是这个想法的话用二分法就麻烦了,你试下我那个,加上查找位置,返回坐标功能,也只是加一句代码而已
没必要实现个功能就要用到繁琐的代码啊
作者: 颜秉武    时间: 2011-12-4 10:49
  1. public class Halfsearch {
  2.         public static void main(String[] args) {
  3.                 // TODO Auto-generated method stub
  4.                 int[] arr = { 1, 3, 5, 7, 8, 12, 45, 89 };
  5.                 int index = halfsearch(arr, 14);
  6.                 System.out.println("应插入的索引位置是"+index);
  7.         }

  9.         public static int halfsearch(int[] arr, int key) {
  10.                 for (int i = 0; i < arr.length; i++) {
  11.                         if (arr[i] == key || arr[i] > key) {
  12.                                 return i;
  13.                         }
  14.                 }
  15.                 return arr.length;
  16.         }
  17. }
复制代码
这样就好了,我有点想不懂,你一定要用哪种方法的目的是什么?在试验什么
作者: 颜秉武    时间: 2011-12-4 10:52
package dsfdghd;

public class Halfsearch {
        public static void main(String[] args) {
                // TODO Auto-generated method stub
                int[] arr = { 1, 3, 5, 7, 8, 12, 45, 89 };
                halfsearch(arr, 7);
        }

        public static void halfsearch(int[] arr, int key) {
                for (int i = 0; i < arr.length; i++) {
                        if (arr[i] == key ) {
                                System.out.println("所给数字在"+i+"号索引");
                        }else if(arr[i] > key){
                                System.out.println("所给数字应插入在"+i+"号索引");
                        }
                }
                System.out.println("所给数字应插入在"+arr.length+"号索引");
        }
}
作者: 杨银川    时间: 2011-12-4 11:12
永无止境的、 发表于 2011-12-4 10:49
这样就好了,我有点想不懂,你一定要用哪种方法的目的是什么?在试验什么

你这个方法的确很简单，很好，其实以前看毕老师的视频的时候，有一集讲到了二分查找法，我当时就把数组中的数目改了一下，就出问题了，这也是我当时的一个疑问，就是想看看用二分法怎么解决这个问题，不过，你给的方法简单易懂，多向你学习啊
作者: 颜秉武    时间: 2011-12-4 11:30
能帮助到你就是最好的
作者: 刘志祥    时间: 2011-12-4 11:34
楼主的代码直观上讲，代码复用性不是很好。



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2