Belajar Algoritma Binary Search Dengan Java

Omjebs > Tech > Belajar Algoritma Binary Search Dengan Java
code coder coding computer

Belajar Algoritma Binary Search Dengan Java

Binary Search digunakan untuk mencari index elemet array. Pencarian dengan binary search ini lebih efisien dibandingkan pencarian secara linear.

Pencarian Biner (Binary Search) dilakukan untuk :

  • memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam array, khususnya untuk jumlah data yang sangat besar ukurannya.
  • Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan).
  • Syarat utama untuk pencarian biner adalah data di dalam array harus sudah terurut.

Contoh sederhana dalam progam java.

class BinarySearchExample{  
 public static void binarySearch(int arr[], int first, int last, int key){  
   int mid = (first + last)/2;  
   while( first <= last ){  
      if ( arr[mid] < key ){  
        first = mid + 1;     
      }else if ( arr[mid] == key ){  
        System.out.println("Element is found at index: " + mid);  
        break;  
      }else{  
         last = mid - 1;  
      }  
      mid = (first + last)/2;  
   }  
   if ( first > last ){  
      System.out.println("Element is not found!");  
   }  
 }  
 public static void main(String args[]){  
        int arr[] = {1,5,6,7,9};  
        int key = 7;  
        int last=arr.length-1;  
        binarySearch(arr,0,last,key);     
 }  
}  

Dalam kasus diatas kita mencari angka 9

psudocode

ambil tengah dari array, mid=first+last div 2 , yaitu 0+4/2=2
looping selama fist lebih kecil sama dengan last
cek Array[mid] lebih kecil dari key yang dicari, 6<9
    jika, ya= first=mid+1, 2+1=3
    jika tidak= cek array[mid] sama dengan key, 6==9,
                    jika ya maka index di temukan, di mid, dan return mid
    jika kondisi di atas tidak ditemukan, maka last=mid-1
    mid=first+last/2, 3+4/2=3

looping kedua first=3<4
cek Array[mid] lebih kecil dari key yg di cari, 7<9
    jika, ya= first=mid+1, 3+1=4
    jika tidak= cek array[mid] sama dengan key, 6==9,
            jika ya maka index di temukan, di mid, dan return mid
    jika kondisi di atas tidak ditemukan, maka last=mid-1
    
    mid=first+last/2, 4+4/2=4       
looping ketiga first=4<=4
cek Array[mid] lebih kecil dari key yg di cari, 9<9
    jika, ya= first=mid+1, 4+1=4
    jika tidak, cek 9=9
        jika ya return index yang ditemukan

        Jika selama looping tidak ada ditemukan, maka first akan lebih besar dari last, 
        dan return data tidak ditemukan

algorima binary search sangat simple dan mempermudah untuk pencarian.

Binary Search Dengan Recursive

class BinarySearchExample1{  
    public static int binarySearch(int arr[], int first, int last, int key){  
        if (last>=first){  
            int mid = first + (last - first)/2;  
            if (arr[mid] == key){  
            return mid;  
            }  
            if (arr[mid] > key){  
            return binarySearch(arr, first, mid-1, key);//search in left subarray  
            }else{  
            return binarySearch(arr, mid+1, last, key);//search in right subarray  
            }  
        }  
        return -1;  
    }  
    public static void main(String args[]){  
        int arr[] = {10,20,30,40,50};  
        int key = 30;  
        int last=arr.length-1;  
        int result = binarySearch(arr,0,last,key);  
        if (result == -1)  
            System.out.println("Element is not found!");  
        else  
            System.out.println("Element is found at index: "+result);  
    }  
}  

Java juga memberikan library simple untuk binary search yaitu menggunakan Arrays.binarySearch(arr,key)

import java.util.Arrays;  
class BinarySearchExample2{  
    public static void main(String args[]){  
        int arr[] = {10,20,30,40,50};  
        int key = 30;  
        int result = Arrays.binarySearch(arr,key);  
        if (result < 0)  
            System.out.println("Element is not found!");  
        else  
            System.out.println("Element is found at index: "+result);  
    }  
}  
0 0 vote
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x