Binärsuche. Drucken Sie die Elemente aus, die mit dem Ziel verglichen werden?

Question

Ich habe Probleme mit diesem Lehrbuchproblem. Welche Änderung müsste ich mit der BinarySearch-Funktion machen, damit die Sequenz von Array-Elementen, die mit dem Ziel verglichen werden, ausgegeben wird?

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

Wenn Sie die Elemente drucken möchten, die dann an das Ziel verglichen werden einfach eine print-Anweisung vor dem Vergleich in der Methode hinzufügen binarySearch:

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

Sie können auch System.out.print("-> "); für eine bessere Darstellung hinzufügen, wenn das Ziel nicht gefunden wurde

Hier sind die Zahlen vor dem Pfeil die Elemente, mit denen das Ziel verglichen wird, und nach einem rrow ist der Rückgabewert der Methode.

Ausgang:

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