Chebysheev

Kali ini kita akan belajar sedikit tentang bagaimana sih cara menghitung jumlah iterasi yang dilakukan suatu Algoritma pencarian,
disini saya gunakan BinarySearch, dengan menghitung jumlah iterasi yang terjadi dalam usaha pencarian suatu element kita dapat mengetahui Algoritma Pencarian mana sih yang lebih baik,



oleh karena itu saya pikir tidak ada salahnya untuk belajar tentang menghitung iterasi,disi saya gunakan ukuran Array 1000, wah besar juga yah,,
masak harus diisi manual tiap elementnya, Gempor tangan kalo begitu,,
tapi ada solusinya, biar mudah saya coba gunakan class Random yang terdapat pada
package java.util.Random, 
BinarySearch akan bisa digunakan jika data terlebih dahulu diUrutkan,
dalam Document sebelumnya tentang BinarySearch datanya belum diurutkan karena sudah disetting oleh penulis terlebih dahulu programnya berjalan lancar,, hahaha
untuk mengurutkan Array saya pakai method sort() yang terdapat pada package java.util.Arrays()

langsung aj deh,,this is the Code


//Start Code
import java.util.Random;
import java.util.Arrays;

public class TestBinarySearch {
  private static final int SIZE = 10000;
  private static final int START = 0;
  private static final int RANGE = 10000;
  private static Random random = new Random();  // inisiasi class Random
  private static int count = 0;

  public static void main(String[] args) {
    int[] a = new int[SIZE];                                      // inisiasi besar Array
    load(a, START, RANGE);                                 // mengisi Array
    Arrays.sort(a);                                                   // mengurutkan Array yang telah diisi
    search(a, random.nextInt(10000));
    System.out.println(count + " iterations");
  }

  public static void load(int[] a, int start, int range) {// method ini berfungsi
                                                                             // mengisi Array
    for (int i = 0; i < a.length; i++) {
      a[i] = start + random.nextInt(range);                // mangacak 5-digit angka lalu
                                                                            // dimasukkan kedalam a[i]
    }
  }

  public static int search(int[] a, int x) {                  // method search yang meng-implementasi
                                                                           // algoritma pencarian BinarySearch
    int lo = 0;
    int hi = a.length;
    while (lo < hi) {
      ++count;
      int i = (lo + hi)/2;
      if (a[i] == x) {
        return i;
      } else if (a[i] < x) {
        lo = i+1;
      } else {
        hi = i;
      }
    }
    return -1;
  }
}//End Code


hasilnya setelah dicompile dan di run adalah :
14 iterations
 
jadi ada 14 perulangan dalam mencari data,
semoga bermanfaat, jika ada yang ingin ditanyakan silakan,
: )