A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 黄嵘才 中级黑马   /  2012-12-19 13:57  /  1835 人查看  /  2 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

关于二分法查找。
问题:我的代码在执行时会死循环。请问,我该怎么怎么改?
二分法算法,怎么样避免死循环。

  1. public class BinarySearch {
  2.         public static void main(String[] args){
  3.                 /*
  4.                  * 1.原始数,无序的
  5.                  * 2.调用二分查找方法,返馈:没有找到。
  6.                  * 3.
  7.                  */
  8.                 int[] data = {12,23,34,56,21,32,45,67,12,45,23,21,4,3,6,9};
  9.                 int key =13;
  10.                 boolean result = binarySearch(key,data);
  11.                 System.out.print(result);
  12.         }

  13.         private static boolean binarySearch(int key, int[] data) {
  14.                 //
  15.                 //需要对data[]进行排序。调用排序方法。返回排序结果
  16.                
  17.                 int[] date = sort(data);
  18.                 int left=0;
  19.                 int right=date.length-1;
  20.                 int middle;
  21.                 while(left<=right){
  22.                         middle = (left+right+1)/2;
  23.                         if(date[middle]==key) return true;
  24.                         else if(key<date[middle]) right = middle+1;
  25.                         else if(key>date[middle]) left = middle-1;
  26.                 }
  27.                 return false;
  28.         }

  29.         private static int[] sort(int[] data) {
  30.                 // 顺序排序
  31.                
  32.                 for(int i=0; i<data.length; i++){
  33.                         for(int j=0; j<data.length; j++){
  34.                                 if(data[i]<data[j]){
  35.                                         int temp = data[i];
  36.                                         data[i] = data[j];
  37.                                         data[j] = temp;       
  38.                                 }
  39.                                
  40.                         }
  41.                 }
  42.                 return data;
  43.                
  44.         }
  45. }
复制代码

2 个回复

倒序浏览
本帖最后由 高境 于 2012-12-19 15: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;
}

评分

参与人数 1技术分 +1 收起 理由
崔政 + 1

查看全部评分

回复 使用道具 举报
      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;
        }

我这个方法能找到,希望对你有用!
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马