java - 二分查找。打印出与目标进行比较的元素？

Question

我正在努力解决这个教科书问题。我需要对 BinarySearch 函数进行哪些修改才能打印出与目标进行比较的数组元素的序列？

public class BinarySearch {

public static int binarySearch(int[] A, int p, int r, int target) {
   int q;
   if(p > r) {
      return -1;
   }else {
      q = (p + r)/2;
      if(target == A[q]) {
         return q;
      } else if (target < A[q]) {
          return binarySearch(A, p, q-1, target);
      } else {
          return binarySearch(A, q+1, r, target);
      }
   }
}

public static void main(String[] args) {
   int[] B = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

   System.out.println(binarySearch(B, 0, B.length-1, 7));
   System.out.println(binartSearch(B, 0, B.length-1, 2));
   System.out.println(binarySearch(B, 0, B.length-1, 11));
  }
}

Answer 1

如果您想打印与目标进行比较的元素，只需在方法中的比较之前添加一条打印语句binarySearch:

q = (p + r)/2;
System.out.print(A[q]+" ");  //  <---- here
if(target == A[q]) {
    System.out.print("-> "); //  <---- here
    return q;
} 

如果未找到目标，您还可以添加System.out.print("-> ");以获得更好的表示

if(p > r) {
   System.out.print("-> "); // <-- here
   return -1;
}

这里箭头之前的数字是与目标进行比较的元素，箭头之后是方法的返回值。

输出:

5 8 6 7 -> 6
5 2 -> 1
5 8 9 10 -> -1