在位数组中搜索成为无限循环

Question

我正在尝试在二元数组中编写搜索算法。请查看升序函数，我正在打印"lo"。当我运行此代码时，它会一直打印该"lo"数字。我不明白为什么它在那里变成无限循环。这是我的代码：

public class bitonicArray {
public int ascending(int[] a, int key, int lo, int hi) {
int mid = lo+(hi-lo)/2;
while(lo<=hi) {
if (key<a[mid]) hi = mid-1;
else if (key>a[mid]) {
lo=mid+1;
System.out.println(lo);
}
else return mid;
}
return -1;
}
public int descending(int[] a, int key, int lo, int hi) {
int mid=lo+(hi-lo)/2;
while(lo<=hi) {
if(key<a[mid]) lo = mid+1;
else if(key>a[mid]) {
hi = mid-1;
}
else return mid;
}
return -1;
}
public int bitonicPoint(int[] a) {
int hi = a.length-1;
int lo = 0;
int mid = (hi-lo)/2;
while(mid<=hi) {
if (a[mid-1] < a[mid] && a[mid+1]>a[mid]) mid = mid + 1;
else if (a[mid-1] > a[mid] && a[mid+1]<a[mid]) mid = mid - 1;
else if (a[mid-1]<a[mid] && a[mid+1]<a[mid]) return mid;
}
return -1;
}
public int ind(int[] a, int key) {
int lo = 0;
int hi = a.length-1;
int bit = bitonicPoint(a);
int asc = ascending(a, key, lo, bit-1);
System.out.println(asc);
int desc = descending(a, key, bit+1, hi);
if (asc != -1) {
System.out.println(asc);
return asc;
}
else if (desc != -1) return desc;
else return bit;        
}
public static void main(String[] args) {
int n[]= {1,3,4,6,9,14,11,7,2,-4,-9};
bitonicArray ba = new bitonicArray();
System.out.println(ba.ind(n, 6));   
}
}

请帮忙。我对Java很陌生。我是Python用户。尝试学习Java。

Answer 1

在代码片段的这一部分中，您不会更新mid值

public int ascending(int[] a, int key, int lo, int hi) {
int mid = lo+(hi-lo)/2;
while(lo<=hi) {
if (key<a[mid]) hi = mid-1;
else if (key>a[mid]) {
lo=mid+1;
System.out.println(lo);
}
else return mid;
}
return -1;
}

最初，当从ind函数调用此函数时，lo的值为 0，hi值为 4。 因此，中间值为 2。 因此while循环中，它进入了这一部分：

else if (key>a[mid]) {
lo=mid+1;
System.out.println(lo);
}

因此，您打印了第一个lo值，但随后您更新了lo值，但没有mid. 因此，每次mid都在 2 和 while 循环中，每次它都进入相同的代码片段。您需要更新mid的值，因为它依赖于lo和hi，并且在上面的else if部分中，您更新了lo的值。

更正后的代码是：

public int ascending(int[] a, int key, int lo, int hi) {
int mid = 0;
while(lo<=hi) {
mid = lo+(hi-lo)/2;
if (key<a[mid]) hi = mid-1;
else if (key>a[mid]) {
lo=mid+1;
System.out.println(lo);
}
else return mid;
}
return -1;
}