黑马程序员技术交流社区

标题: 我的二分法查找法的疑问。 [打印本页]

---

作者: 黄嵘才    时间: 2012-12-19 13:57
标题: 我的二分法查找法的疑问。
关于二分法查找。
问题：我的代码在执行时会死循环。请问，我该怎么怎么改？
二分法算法，怎么样避免死循环。

1. 
   
2. public class BinarySearch {
   
3.         public static void main(String[] args){
   
4.                 /*
   
5.                  * 1.原始数，无序的
   
6.                  * 2.调用二分查找方法，返馈：没有找到。
   
7.                  * 3.
   
8.                  */
   
9.                 int[] data = {12,23,34,56,21,32,45,67,12,45,23,21,4,3,6,9};
   
10.                 int key =13;
    
11.                 boolean result = binarySearch(key,data);
    
12.                 System.out.print(result);
    
13.         }
    
14. 
    
15.         private static boolean binarySearch(int key, int[] data) {
    
16.                 //
    
17.                 //需要对data[]进行排序。调用排序方法。返回排序结果
    
18.                
    
19.                 int[] date = sort(data);
    
20.                 int left=0;
    
21.                 int right=date.length-1;
    
22.                 int middle;
    
23.                 while(left<=right){
    
24.                         middle = (left+right+1)/2;
    
25.                         if(date[middle]==key) return true;
    
26.                         else if(key<date[middle]) right = middle+1;
    
27.                         else if(key>date[middle]) left = middle-1;
    
28.                 }
    
29.                 return false;
    
30.         }
    
31. 
    
32.         private static int[] sort(int[] data) {
    
33.                 // 顺序排序
    
34.                
    
35.                 for(int i=0; i<data.length; i++){
    
36.                         for(int j=0; j<data.length; j++){
    
37.                                 if(data[i]<data[j]){
    
38.                                         int temp = data[i];
    
39.                                         data[i] = data[j];
    
40.                                         data[j] = temp;       
    
41.                                 }
    
42.                                
    
43.                         }
    
44.                 }
    
45.                 return data;
    
46.                
    
47.         }
    
48. }
    

复制代码

---

作者: 高境    时间: 2012-12-19 14:13


第24行 middle = (left+right+1)/2;应该改为middle = (left+right)/2; 举个例子，如果第一次，left=0；right=5，那么，运算结果就是middle=2，如果像你那样的话，计算出的结果就会是middle=3
其实二分法还有另外一种方法如下
public static int halfSearch(int[] arr,int key)
{
  int min,max,mid;
  min = 0;
  max = arr.length-1;
  mid = (max+min)/2;//折半
  while(arr[mid]!=key)//while循环
  {
   if(key>arr[mid])
    min = mid + 1;//如果要查找的值在中间角标的右边就把最小角标往右移
   else if(key<arr[mid])
    max = mid - 1;//如果要查找的值在中间角标的左边就把最大角标往右移
   if(min>max)
    return -1;//当最小值的角标大于最大值的角标时候，说明没有折半结束，没有找到要找的key
   mid = (max+min)/2;
  }
  return mid;
}

---

作者: Spring up    时间: 2012-12-19 14:26
      public static int binarySearch(int[] arr, int key) {
                //默认的范围是整个数组
                int begin = 0;//范围的开始
                int end = arr.length-1;//范围的结束
                int m; //范围的中心点
                while(begin <= end) {
                        m = (begin + end) / 2;//找到当前范围的中心。
                        if(arr[m] == key) {//让key与中心点元素进行比较，如果相等，说明找到了。
                                return m;//返回m.
                        }
                        if(key > arr[m]) {//当key比大于中心点元素
                                begin = m + 1;//开始位置从中心点+1
                        } else {
                                end = m - 1;//当key比中心点元素小，那么结束位置就是中间点-1
                        }
                }
                return -1;
        }

我这个方法能找到，希望对你有用！

---

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

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