Pertanyaan Java menghitung jumlah pencarian biner perbandingan


Saya menulis kode berikut untuk pencarian biner di java:

import java.util.Arrays;

class BinarySearch  {
    public static int binarySearch(double[] arr, double x, int high, int low)   {
        int mid=(high+low)/2;
        if(high==low || low==mid || high==mid)  {
            return -1;
        }
        if(arr[mid]<x)  {
            return binarySearch(arr, x, high, mid);
        }
        else if(arr[mid]>x) {
            return binarySearch(arr, x, mid, low);
        }
        else if(arr[mid]==x)    {
            return mid;
        }
        return -1;
    }

    public static void main(String args[])  {
        int n=1000;
        double array[] = new double[n];
        for (int i=0; i<100; i++)   {
            for (int k = 0; k < n; k++) {
                double r = Math.random();
                r = r * 100;
                r = Math.round(r);
                r = r / 100;
                array[k] = r;
            }
            Arrays.sort(array);
            double search = Math.random();
            search = search * 100;
            search = Math.round(search);
            search = search / 100;
            int result=binarySearch(array, search, n, 0);
            if (result == -1)
                System.out.println(search +" befindet sich nicht im Array.");
            else
                System.out.println(search+" befindet sich im Array an der Stelle "+(result)+".");
    }
}

}

Saya ingin melihat jumlah perbandingan yang perlu dilakukan oleh pencarian biner untuk menemukan nomor tersebut, tetapi saya tidak tahu cara mengimplementasikannya. Saya sudah membuat lingkaran sehingga saya bisa melihat rata-rata perbandingan tetapi saya tidak tahu bagaimana mendapatkan jumlah perbandingan.


4
2018-06-09 16:33


asal


Jawaban:


Anda dapat melakukan ini untuk membuat semuanya tetap sederhana.

private static int comparisions = 0;

public static int binarySearch(double[] arr, double x, int high, int low) {
    int mid = (high + low) / 2;
    if (high == low || low == mid || high == mid) {
        comparisions++;
        return -1;
    }
    if (arr[mid] < x) {
        comparisions++;
        return binarySearch(arr, x, high, mid);
    } else if (arr[mid] > x) {
        comparisions++;
        return binarySearch(arr, x, mid, low);
    } else if (arr[mid] == x) {
        comparisions++;
        return mid;
    }
    return -1;
}

public static void main(String args[]) {
    int n = 1000;
    double array[] = new double[n];
    for (int i = 0; i < 100; i++) {
        for (int k = 0; k < n; k++) {
            double r = Math.random();
            r = r * 100;
            r = Math.round(r);
            r = r / 100;
            array[k] = r;
        }
        Arrays.sort(array);
        double search = Math.random();
        search = search * 100;
        search = Math.round(search);
        search = search / 100;
        int result = binarySearch(array, search, n, 0);
        System.out.println("Number of comparisions " +  comparisions);
        if (result == -1)
            System.out.println(search + " befindet sich nicht im Array.");
        else
            System.out.println(search + " befindet sich im Array an der Stelle " + (result) + ".");
    }

}

5
2018-06-09 16:42



Deklarasikan sebuah int di bagian atas kode Anda, dan kenaikan itu sebelum setiap pernyataan kembali (karena itulah langkah terakhir dari perbandingan).

int compares = 0;

//other code

compares++;
return blahblah;

2
2018-06-09 16:38



Anda dapat meneruskan jumlah perbandingan ke bawah rantai permintaan dari metode rekursif Anda, seperti ini:

public static int binarySearch(double[] arr, double x, int high, int low, int cmp) {
    ...
    if(arr[mid]<x)  {
        // We made one additional comparison
        return binarySearch(arr, x, high, mid, cmp+1);
    } else if(arr[mid]>x) {
        // We made two additional comparisons
        return binarySearch(arr, x, mid, low, cmp+2);
    } else {
        // We made two additional comparisons.
        // We are about to return the result, so print the final number of comparisons:
        System.out.println("Performed "+(cmp+2)+" comparisons.");
        return mid;
    }
}

Lewati nol untuk cmp argumen dalam panggilan dari main.


1
2018-06-09 16:39



Deklarasikan varibel di luar binarysearch() 

import java.util.Arrays;
   class BinarySearch  {
      int num_of_calls = 0;
      public static int binarySearch(double[] arr, double x, int high, int low)   {
         num_of_calls++;
        ...
        }

num_of_calls akan berisi jumlah berapa kali fungsi rekursif dipanggil.


0
2018-06-09 16:42