黑马程序员技术交流社区

标题: 关于折半查找的一点问题 [打印本页]

---

作者: 王桂丽    时间: 2012-8-3 00:56
标题: 关于折半查找的一点问题
*
需求：在给定的数组中查找所给定的数字
*/
class  BSort2
{
public static int select(int[]arr,int key)//定义函数，将数组与指定的数字传进去
{
  int min,max,mid;
  min=0;
  max=arr.length;
  mid=(min+max)/2;
  while(key!=mid)
   {
    if (key>mid)
     {
      min=mid+1;
     }
    else
     {
      max=mid-1;
     }
     mid=(min+max)/2;
     return mid;
   }
   return -1;
   
}
public static void main(String[] args)
{
  int[] arr={1,5,7,8,9,5,7};
  PrintAarr(arr);//调用打印数组的方法
  select(arr,8);//调用查找的方法
  PrintAarr(arr);//调用打印数组的方法
  
}
public static void PrintAarr(int[]arr)//定义打印数组中各值的方法，通过遍历的形式
{
  System.out.print("[ ");
  for(int x=0;x<arr.length;x++)
   {
   
   if (x<arr.length-1)
   {
    System.out.print(x+" , ");
   }
   else
   {
    System.out.println(x+" ]");
   }
   }
}
}



疑问：不知道代码出错在哪里，为什么运行后结果是  [0,1,2,3,4,5,6]
这个结果是怎么产生的？


file:///C:/Users/samsung/AppData/Roaming/Tencent/Users/2531988876/QQ/WinTemp/RichOle/E8WJ7E]%7B_Y4ZJ%7B%7D$@%7B5HM%60F.jpg

未命名.jpg (14.96 KB, 下载次数: 64)

下载附件

2012-8-3 00:56 上传

---

作者: 周坤    时间: 2012-8-3 01:06
那想要什么结果，折半查找是查找，数组本身并没有变化，
打印数组还是那个数组。

---

作者: 余明辉    时间: 2012-8-3 01:20
你的printArr方法中的输出语句写错了，你注意看下，你输出来的是循环次数，不是数组中的值
而且你的2分查找也写错了，应该这样写
        public static int binarySearch(int[] a, int num) {
                //判断数组是否为空，为空返回-1
                if (a.length == 0) return -1;
               
                //定义三个数，开始，结尾，和中间的数
                int startPos = 0;
                int endPos = a.length-1;
                int m = (startPos + endPos) / 2;
               
               
                while(startPos <= endPos) {                //开始的数不能小于最后的数
                        if(num == a[m]) return m;         //2分法的时候，num刚好等于数组中间那个数
                        if(num > a[m]) {
                                startPos = m + 1;  //+1是因为：要把m右边剩下再次2分，所以要m+1
                        }
                        if(num < a[m]) {
                                endPos = m - 1;                //-1是因为：要把m左边剩下再次2分，所以要m-1
                        }
                        m = (startPos + endPos) / 2;
                }
               
                return -1;
        }
希望可以帮到你，我已经写上了注释帮助你理解，2分查找这种算法的东西，需要认真点分析程序执行的顺序，才不会写错

---

作者: 余明辉    时间: 2012-8-3 01:26
还有一点忘了提醒你，用折半法查找一个值的时候，要先排序，你的源码没有排序，因为折半法每次都是查找2个游标中间的那个数，如果那个不是你要找的那个，就会在剩下的某一半中找，另一半是不找的了

---

作者: 谭培龙    时间: 2012-8-3 01:46

1. import java.util.*;
   
2. class  BSort2
   
3. {
   
4. public static int select(int[]arr,int key)//定义函数，将数组与指定的数字传进去
   
5. {
   
6.   int min,max,mid;
   
7.   min=0;
   
8.   max=arr.length-1;//这里应该是arr.length-1,因为角标是从0开始 -1防止角标越界。 mid=(min+max)/2;
   
9.   while(key!=mid)
   
10.    {
    
11.     if (key>mid)
    
12.      {
    
13.       min=mid+1;
    
14.      }
    
15.     else
    
16.      {
    
17.       max=mid-1;
    
18.      }
    
19.      mid=(min+max)/2;
    
20.      return mid;
    
21.    }
    
22.    return -1;
    
23.    
    
24. }
    
25. 
    
26. public static void main(String[] args)
    
27. {
    
28.   int[] arr={1,5,7,8,9,5,7};//这个数组没有排序,无法实现折半查找。如果想实现折半,必须先排序。        
    
29. Arrays.sort(arr);//排序
    
30.   PrintAarr(arr);//调用打印数组的方法
    
31.   int index = select(arr,8);//调用查找的方法,把这个值赋给index。
    
32.   System.out.println(index);
    
33.   
    
34. }
    
35. public static void PrintAarr(int[]arr)//定义打印数组中各值的方法，通过遍历的形式
    
36. {
    
37.   System.out.print("[ ");
    
38.   for(int x=0;x<arr.length-1;x++)//这个for循环只打印了arr数组的角标。
    
39.    {
    
40.    
    
41.    if (x!=arr.length-1)
    
42.    {
    
43.     System.out.print(arr[x]+" , ");//如果想打印角标的值应加上arr[]
    
44.    }
    
45.    else
    
46.    {
    
47.     System.out.println(arr[x]+" ]");
    
48.    }
    
49.    }
    
50. }
    
51. }

复制代码

折半必须是有序的数组才可以。注意数组用length方法时根据需求看是否需要-1防止角标越界

---

作者: 陈少文    时间: 2012-8-3 07:18


折半查找：前提，数组元素为有序元素。

目的：查找元素8，所在数组的角标。  


class  DemoArr
{

public static void main(String[] args)
{
        int[] arr={1,5,7,8,9};
        int  index = select(arr,8);//调用查找的方法
         System.out.println(index);

}

public static int select(int[]arr,int key)//定义函数，将数组与指定的数字传进去
{
          int min,max,mid;
          min=0;
          max=arr.length-1;    //一定要-1因为它表示角标值而不是元素个数
           mid=(min+max)/2;
           while(key!=mid)
   {
    if (key>mid)
     {
             min=mid+1;
     }
    else
     {
            max=mid-1;
     }
           mid=(min+max)/2;
           return mid;
   }
         return -1;
}

｝

---

作者: 王峰    时间: 2012-8-3 10:05


//楼主，在给定的数组中查找给定的数字，我给你修改了下，你比较你源代码看下.................
//原数组{1,5,7,8,9,5,7}，假如这里要查找8，...............

//折半查找法的一个前提是必须对数组进行排序，然后才能折半法............................

//楼主所以你还得定义一个排序的方法,当然楼主的打印方法也写错了，我给你修改了，你卡看..........................

public  class  BSort2
{
        
//定义一个排序的方法...............................................
public static void paixu(int [] str){
        
        //用冒泡排序法排序...........................................
        
        for (int i = 0; i < str.length; i++){
                for (int j = str.length-1; j > i; j --){
                        if (str[j] < str[j-1]){
                                int temp = str[j];
                                str[j] = str[j-1];
                                str[j-1] = temp;
                        }
                }
        }
}

//对查找的方法进行修改。。。。。。。。。。。。。

public static void select(int[]arr,int key)//定义函数，将数组与指定的数字传进去
{
  int min,max,mid;
  min=0;
  max=arr.length;
  mid=(min+max)/2;
  
  //这里修改这条语句。。。。。。。。。。。。。。
  //while(key!=mid)
  
  while(true)
   {
          //这里修改这条语句。。。。。。。。。。。。。。
         
    //if (key>mid)
          if (key > arr[mid])
     {
      min=mid+1;
     }
    else
     {
      max=mid-1;
     }
          //增加2条if语句
          if (key == arr[mid]){
                  System.out.println("要查找的关键字 \"" + key + "\" 存在;\n它在排序后数组中的第"+(mid+1)+"个位置");
                  break;
          }
          if (min > max){
                  System.out.println(key + "关键字不存在");

                  break;
          }
     mid=(min+max)/2;
     //这里去掉这条语句。。。。。。。。。。。。。。。。。。。
    // return mid;
   }
  //这里去掉这条语句。。。。。。。。。。。。。。。。。。。
  // return -1;
   
}
public static void main(String[] args)
{
  int[] arr={1,5,7,8,9,5,7};
  
  //打印排序前的数组。。。。。。。。。。。。。
  System.out.println("排序前的数组");
  PrintAarr(arr);//调用打印数组的方法
  //调用排序方法。。。。。。。。。。。。。。。。。。。。
  paixu(arr);
  
  //打印排序后的数组。。。。。。。。。。。。。
  System.out.println("排序后的数组");
  PrintAarr(arr);//调用打印数组的方法
  
  select(arr,8);//调用查找的方法

  
}

//打印方法楼主也写错了，我做了修改...............
public static void PrintAarr(int[]arr)//定义打印数组中各值的方法，通过遍历的形式
{
  System.out.print("[ ");
  for(int x=0;x<arr.length;x++)
   {
   
   if (x < arr.length-1)
   {
           //这里不是输出x,修改。。。。。。。。。。。
    //System.out.print(x+" , ");
           System.out.print(arr[x]+" , ");
   }
   else
   {
    //System.out.println(x+" ]");
           System.out.println(arr[x]+" ]");

   }
   }
}
}

22222222222.jpg (19.39 KB, 下载次数: 59)

下载附件

2012-8-3 10:08 上传

修改后的结果

---

作者: 王桂丽    时间: 2012-8-3 13:30

余明辉 发表于 2012-8-3 01:20
你的printArr方法中的输出语句写错了，你注意看下，你输出来的是循环次数，不是数组中的值
而且你的2分查找 ...

明白了~

---

作者: 王桂丽    时间: 2012-8-3 13:31

谭培龙 发表于 2012-8-3 01:46
折半必须是有序的数组才可以。注意数组用length方法时根据需求看是否需要-1防止角标越界 ...

明白了，谢谢~

---

作者: 王桂丽    时间: 2012-8-3 13:40
问题已解决

---

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

黑马程序员IT技术论坛 X3.2