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

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© yekong262 中级黑马   /  2014-1-22 10:05  /  1351 人查看  /  4 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 yekong262 于 2014-1-22 10:49 编辑
  1. int [] arr={1,5,6,7};给定一个函数。假如key=8这个函数如何在下面循环中运行的 代码运行顺序。。
复制代码

  1. public static int halfSearch(int [] arr,int key)
  2.         {
  3.                 int max ,min,mid;
  4.                 max=arr.length-1;
  5.                 min=0;
  6.                 mid=(max+min)/2;
  7.                 while (key!=arr[mid])
  8.                 {
  9.                        
  10.                         if (key>arr[mid])
  11.                                 min=mid+1;
  12.                         else if (key<arr[mid])
  13.                                 max=mid-1;
  14.                         
  15. mid=(max+min)/2;
  16.                
  17.                 }

  18.                 return mid;
复制代码
int [] arr={1,5,6,7};
max=3
min=0
mid=3+0/2=1
第一次运行;8!=arr[1]=5  8>5
min=1+1
mid=2+3/2=2
第2次运行; 8!=arr[2]=6
8>6
min =2+1
mid=3+3/2=3
第3次运行; 8!=arr[3]=7
8>7
min=3+1
mid=4+3/2=3
第4次运行; 8!=arr[3]=7
8>7
min=3+1
mid=4+4/2=4
第5次运行;8!=arr[4]这个时候角标已经越界。怎么还能运行
8>arr[4] 没有这个角标。

评分

参与人数 1技术分 +1 收起 理由
黄晓鑫 + 1

查看全部评分

4 个回复

倒序浏览
会调试程序吗?像这类问题,你要学会调试就行
回复 使用道具 举报
二分查找吧,哥们,你忽略了一种情况,如果min<max呢?
我改写了你的代码,你把
  1. if(min<max)
  2.                                 return -1;//没有找到
复制代码
这句话注释掉就可以查看每次循环输出的结果,然后你就会发现原因的
附上一代代码:

  1. public class HalfFind {

  2.         public static void main(String[] args) {
  3.                 int [] arr={1,5,6,7};
  4.                 System.out.println(halfSearch2(arr, 8));
  5.         }

  6.         public static int halfSearch(int[] arr, int key) {
  7.                 int max, min, mid;
  8.                 max = arr.length - 1;
  9.                 min = 0;
  10.                 mid = (max + min) / 2;
  11.                 while (key != arr[mid]) {
  12.                         System.out.println(min+"\t"+mid+"\t"+max+"\t"+arr[mid]);
  13.                         if(min<max)
  14.                                 return -1;//没有找到
  15.                         if (key > arr[mid])
  16.                                 min = mid + 1;
  17.                         else if (key < arr[mid])
  18.                                 max = mid - 1;
  19.                         mid = (max + min) / 2;
  20.                 }
  21.                 return mid;

  22.         }
  23.         public static int halfSearch2(int[] arr, int key) {
  24.                 int lowerBound = 0;
  25.                 int upperBound = arr.length - 1;
  26.                 int curIn;
  27.                
  28.                 while(true){
  29.                         curIn = (lowerBound + upperBound)/2;
  30.                         if(arr[curIn] == key){
  31.                                 return curIn;
  32.                         }else if(lowerBound > upperBound){
  33.                                 return -1;
  34.                         }else{
  35.                                 if(arr[curIn] < key){
  36.                                         lowerBound = curIn + 1;
  37.                                 }else{
  38.                                         upperBound = curIn - 1;
  39.                                 }
  40.                         }
  41.                 }
  42.         }
  43. }
复制代码

评分

参与人数 1技术分 +1 收起 理由
黄晓鑫 + 1

查看全部评分

回复 使用道具 举报
浮出一个美 发表于 2014-1-22 10:31
二分查找吧,哥们,你忽略了一种情况,如果min

哦 我知道哪里错。~
回复 使用道具 举报
如果查找不到的话应该会出现一种min > max的情况吧,楼上的朋友是不是写反了?
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马