Pencarian Linear Pada Array

Pencarian atau searching adalah proses untuk menemukan elemen yang spesifik di dalam suatu array, dan ini adalah hal yang umum dilakukan pada proses pemrograman. Berbeda dengan pencarian secara binary, pencarian secara linear merupakan suatu metode untuk menemukan elemen tertentu di dalam suatu list, dengan memeriksa satu persatu setiap elemen, pada satu waktu dan secara berurutan sampai dengan target ditemukan.

linear search


Cara ini merupakan yang paling simpel untuk algoritma pencarian. Untuk array dengan jumlah elemen sebanyak Z, maka kasus terbaik adalah jika nilai yang dicari merupakan elemen pertama, karena hanya memerlukan satu kali saja perbandingan diperlukan.

Sedangkan kasus terburuk yaitu bila nilai yang dicari tidak berada di dalam list atau hanya ada pada akhir dari list, yang berarti memerlukan perbandingan dengan jumlah Z kali untuk menemukan elemen tersebut.

Proses linear search tidak memerlukan pengurutan data terlebih dahulu.

Skenario kinerja terburuk dari pencarian secara linear adalah keharusan untuk melakukan loop terhadap keseluruhan collection, walaupun target yang dicari adalah elemen terakhir ataupun tidak ditemukan di dalam list.

Dengan kata lain, jika anda memiliki sejumlah Z elemen di dalam array, maka skenario terburuknya adalah perulangan akan dilakukan sebanyak Z kali.

Contoh linear search:


public class MetodeLinear {
 
    public static int pencarianLinear(int[] myArray, int myKey){
        
        int size = myArray.length;
        for(int i=0;i<size;i++){
            if(myArray[i] == myKey){
                return i;
            }
        }
        return -1;//jika elemen tidak ditemukan, maka akan nilai -1 akan 
                  //dikembalikan

    }
    
    public static void main(String a[]){
        
        int[] array1= {67, 89, 54, 23, 36, 60, 65, 89, 52, 43};
        int target = 60;
        
        System.out.println("Target "+ target + " ditemukan pada index: "
        + pencarianLinear(array1, target));
        
        int[] array2= {2009, 1879, 2563, 1986, 1790, 1135, 1345, 1197};
        target = 1879;
        
        System.out.println("Target "+ target + " ditemukan pada index: "
        +pencarianLinear(array2, target));
    }
}


Output:
Target 60 ditemukan pada index: 5
Target 1879 ditemukan pada index: 1

Terus bagaimana bila pada array terdapat nilai yang sama atau duplikat?, misalnya:

Nilai target yang dicari adalah 60, dan akan dicari dalam array dengan list elemen 87, 65, 43, 60, 55, 32, 60. Maka nilai array pada index pertama yang akan dikembalikan, dalam hal ini adalah nilai 60 pada index ke 3.

Labels: , ,