如何在递归二进制搜索中显示新中间的位置

Question

所以我的任务是实现递归二分搜索以在整数数组中找到目标值。我将所有代码都关闭了，但是我在这部分中遇到了问题：在每次递归调用中，输出您正在检查的中间值与目标值。如果中间值与目标不匹配，请指出下一轮是否检查搜索阵列的顶部或底部。

这里是我的代码：

public class anArray { 

    private long[] a; // reference to array a in anArray() 
    private int nElems; // number of elements 

    public anArray(int max) // constructor 
    { 
     a = new long[max]; // creates new array 
     nElems = 0; 
    } 

    public int size() // this will return the size of the array, 
    {         // or number of elements 
     return nElems; 
    } 

    public int find(long search) // constructor to find search 
    { 
     return recFind(search, 0, nElems - 1); 
    } 

    private int recFind(long search, int lowerBound, int upperBound) { 
     int mid = (lowerBound + upperBound)/2; 
     if (search == a[mid]) { 
      return mid; // value found at anArray[mid] 
     } else if (lowerBound > upperBound) { 
      return nElems; // can't find it 
     } else // divide range 
     { 
      if (a[mid] < search) // it's in the upper half 
      { 
       return recFind(search, mid + 1, upperBound); 
      } else // it's in the lower half 
      { 
       return recFind(search, lowerBound, mid - 1); 
      } 
     } 
    } 

    public void insert(long v) // put element into array 
    { 
     int j; 
     for (j = 0; j < nElems; j++) // find where it goes 
     { 
      if (a[j] > v) // linear search 
      { 
       break; 
      } 
     } 

     for (int k = nElems; k > j; k--) // move bigger ones up 
     { 
      a[k] = a[k - 1]; 
     } 
     a[j] = v;  // insert it 
     nElems++;  // increment size 
    } 

    public void display() // displays array elements 
    { 
     for (int j = 0; j < nElems; j++) // for each element, 
     { 
      System.out.println(a[j] + " ");  // display it. 
     } 
     System.out.println(" "); 
    } 
} 

而且我的演示：

public class BinarySearchDemo { 

    public static void main(String[] args) { 
     int maxSize = 21; // array size 
     anArray arr;  // reference to array 
     arr = new anArray(maxSize); // create the array 

     arr.insert(45); // insert elements 
     arr.insert(78); 
     arr.insert(98); 
     arr.insert(12); 
     arr.insert(56); 
     arr.insert(45); 
     arr.insert(12); 
     arr.insert(78); 
     arr.insert(63); 
     arr.insert(45); 
     arr.insert(78); 
     arr.insert(45); 
     arr.insert(77); 
     arr.insert(12); 
     arr.insert(80); 
     arr.insert(82); 
     arr.insert(78); 
     arr.insert(54); 
     arr.insert(65); 
     arr.insert(80); 
     arr.insert(50); 

     arr.display(); // displays array 

     int search = 82; // search for item 
     if (arr.find(search) != arr.size()) { 
      System.out.println("Found " + search); 
     } else { 
      System.out.println("Can't find " + search); 
     } 
    } 
} 

感谢所有帮助。

Answer 1

你应该把你的支票if (lowerBound > upperBound)在你的函数的第一张支票，否则你可能会在一个无限循环结束。

这一部分：

输出要检查针对你的目标值中值

可以做那么简单，以下print语句你计算mid后：

System.out.println("Checking mid=" + a[mid] + " against target=" + search); 

此部件适用于：

如果中间值与目标不匹配，请指出下一轮是检查搜索阵列的上半部还是下半部。

同样，只要您确定a[mid]小于或大于search，就可以打印它。

if (a[mid] < search) { 
    System.out.println("examining upper half"); 
} 

同理：

if (a[mid] > search) { 
    System.out.println("examining bottom half"); 
} 

此外，使用{}为您if/else报表，以确保一切都在正确的范围。

应用这些改变你的代码：

private int recFind(long search, int lowerBound, int upperBound) { 
    if (lowerBound > upperBound) { 
     return nElems; // can't find it 
    } 

    int mid = (lowerBound + upperBound)/2; 

    // print mid and target 
    System.out.println("Checking mid= " + a[mid] + " against target=" + search"); 

    if (search == a[mid]) { 
     return mid; // value found at anArray[mid] 
    } 
    else    // divide range 
    { 
     if (a[mid] < search) { // it's in the upper half 
      System.out.println("examining upper half"); 
      return recFind(search, mid+1, upperBound); 
     } 

     else {    // it's in the lower half 
      System.out.println("examining bottom half"); 
      return recFind(search, lowerBound, mid-1); 
     } 
    } 
} 

Answer 2

如果我理解你，那么你需要改变这种

private int recFind(long search, int lowerBound, int upperBound) { 
    int mid = (lowerBound + upperBound)/2; 
    if (search == a[mid]) 
    return mid; // value found at anArray[mid] 
    else if (lowerBound > upperBound) 
    return nElems; // can't find it 
    else { 
    if (a[mid] < search) // it's in the upper half 
     return recFind(search, mid+1, upperBound); 
    else  // it's in the lower half 
     return recFind(search, lowerBound, mid-1); 
    } 
} 

通过添加括号，并打印你的意见已经说了。这就是说，

private int recFind(long search, int lowerBound, int upperBound) { 
    int mid = (lowerBound + upperBound)/2; 
    if (search == a[mid]) { 
    System.out.printf("%d found at pos = %d%n", search, mid); 
    return mid; // value found at anArray[mid] 
    } else if (lowerBound > upperBound) { 
    System.out.printf("%d NOT found return = %d%n", search, nElems); 
    return nElems; // can't find it 
    } else { 
    if (a[mid] < search) { // it's in the upper half 
     System.out.printf("%d search, recurse upper half from position%d%n", 
      search, mid); 
     return recFind(search, mid+1, upperBound); 
    } else {    // it's in the lower half 
     System.out.printf("%d search, recurse lower half from position%d%n", 
      search, mid); 
     return recFind(search, lowerBound, mid-1); 
    } 
    } 
}