折半查找

Question

class IndexSearch{
public static void main{String [] args)
{
 int[] arr={1,2,3,4,5,6,7,8,9,10,11,22,33,44,55,66,77,88,99,100};
 int index=search(arr,77);
System.out.println("index="+index);
}
int search(int arr,key)
{
int min=arr[0];int max=arr.length-1;
int mid=(min+max)/2
while(arr[mid]!=key)
{
if(key>arr[mid])
min=mid+1;
else if(key<arr[mid])
max=mid-1;
mid=(min+max)/2
if(min>max)
return -1；
}
return mid;
}
}
为什么上面的代码会有这种问题：编译没错，100可以查的到，99可以查的到，88可以查的到，77机子就卡的不得动了。各位大神指教一下啊，折半查找。if(min>max)这个条件我知道是在里面查不到的语句，但我不能理解这句。

Answer 1

单看这一句：
public static void main{String [] args)你这代码编译能没错？？？

Answer 2

int min=arr[0];int max=arr.length-1;
这代码有问题吧

Answer 3

 class IndexSearch{
public static void main{String [] args}
{
 int[] arr={1,2,3,4,5,6,7,8,9,10,11,22,33,44,55,66,77,88,99,100};
 int index=search(arr,77);
System.out.println("index="+index);
}
int search(int arr,key)
{
int min=0;int max=arr.length-1;
int mid=(min+max)/2
while(arr[mid]!=key)
{
if(key>arr[mid])
min=mid+1;
else if(key<arr[mid])
max=mid-1;
mid=(min+max)/2
if(min>max)

Answer 4

 return -1；
}
return mid;
}
刚才写快了

Answer 5

我想说的是为什么有些数字查的到，有 些 查不到。会不会是min+max没有括起来的原因。

Answer 6

因为程序没写对，死循环了下面是正确的
public class IndexSearch{

public int search(int[] arr,int key) {
int min=0;int max=arr.length-1;
int mid=(min+max)/2;
while(arr[mid]!=key)
{
if(key>arr[mid]) {
min=mid+1;
mid=(min+max)/2;
} else if(key<arr[mid]) {
max=mid-1;
mid=(min+max)/2;
}
if(min>max) {
return -1;
}
}
return mid;
}
public static void main(String[] args) {

IndexSearch s = new IndexSearch();
int[] arr={1,2,3,4,5,6,7,8,9,10,11,22,33,44,55,66,77,88,99,100};
int index=s.search(arr,77);
System.out.println("index="+index);
}
}

Answer 7

恩 谢了 我老是会丢掉[]，int。
while(arr[mid]!=key)
{
if(key>arr[mid])
min=mid+1;
else if(key<arr[mid])
max=mid-1;
mid=(min+max)/2
这样不可以吗？

Answer 8

我运行楼主程序，没有问题的。
search(arr, 77);
结果：index=16
关于if(min>max)，你思考查到最后剩1个数并且不匹配的情况就理解了。

Answer 9

查一百之后的数，那个if(min>max)我能理解，但是要查一到一百之内，而且里面又没有这个数的话，这个if(min没有大于max的可能性啊）

Answer 10

在一百之外能理解if(min>max)。 而且在一百之内，数组里没有要查的这个数，比如32我就不能理解min会大于max...

Answer 11

我觉得LZ写的挺好的，稍微优化下：
while(arr[mid]!=key)
{
if(key>arr[mid]){
min=mid+1;}
else{
max=mid-1;}
mid=(min+max)/2