Java'da İkili Arama: Yinelemeli, Yinelemeli ve Java Koleksiyonları

Java'da Doğrusal Arama, bir dizideki bir öğeyi bulmak için her zaman başvurulacak yöntem olmuştur. Dizinin her elemanını sırayla arar ve uygulaması son derece kolaydır. Ancak Linear Search'ün eksiklikleri, söz konusu dizi onbinlerce eleman içerdiğinde aşikardır. Bu gibi durumlarda, Binary Search tarafından uygulanan “böl ve fethet” yöntemi, zaman ve mekan karmaşıklığını göz önünde bulunduran programcılar için çok daha verimli ve tercih edilir.

Ikili arama

İkili Arama'da, anahtar (aranan öğe) bulunana kadar bir dizi tekrar tekrar ikiye bölünür. Bölünme sanaldır, yani verilerin bütünlüğü korunur. Her yinelemede dizinin orta değerine odaklanır. Değer, aradığımız anahtara eşitse, döngü veya özyinelemeli işlev sona erer. Aksi halde döngüye devam eder. Ortadaki değer anahtardan büyükse, işlev dizinin ilk yarısına odaklanır ve bunun tersi de geçerlidir. Bu işlem, anahtar bulunana veya tüm dizi yinelenene kadar tekrarlanır.

Doğrusal ve İkili Arama Arasındaki Fark

İkili Arama Algoritması

İkili Arama algoritması aşağıda verilmiştir.

1. Dizinin ilk ve son noktalarını belirleyin. Noktalar, diziye ve aranan anahtara göre her yinelemede ayarlanacaktır.
2. Diziyi yineleyin ve mevcut ilk ve son noktalarınız arasındaki orta değeri karşılaştırın. İlk yinelemede, ilk ve son değişken dizideki gerçek değişkenlerle aynı olacaktır.
3. Anahtar orta değerden büyükse, o değerin dizini yeni "Birinci" değişkende saklanacaktır.
4. Anahtar orta değerden küçükse, o değerin dizini 'Son' değişkeninde saklanacaktır.
5. Bu koşul, iki koşuldan biri gerçekleşene kadar tekrarlanır:
   • Anahtar bulunur.
   • Dizinin tamamı yinelendi.

Hem yinelemeli ikili arama hem de yinelemeli ikili arama için kod aşağıda verilmiştir.

Yinelemeli İkili Arama

Yinelemeli bir yöntemle İkili Arama kodu aşağıda verilmiştir.

import java.util.Scanner;
public class IterativeBinarySearch {
 
    public static void main(String[] args) {
        int arr[] = {1,3,6,8,10};
       
        System.out.println("Enter Number to Search For: ");
        Scanner input = new Scanner (System.in);
       
        int num = input.nextInt();
        int result = BinarySearchIterative(arr,num);
       
        if(result!=-1)
            System.out.println("Value Found at Index #" + result);
        else
            System.out.println("Value Not Found");
    }
 
    public static int BinarySearchIterative(int[] arr, int num){
        //Representing the Start and End Index After Division of Array
        int start = 0;
        int end = arr.length;
 
        //Loop to Iterate Through the Array
        for(int i = 0; iarr[n]){
                start = n;
            }
            //If number to search for is greater than the arr value at index 'n'               
            else{
                end = n;
            }
        }
        //If number isn't found, return -1
        return -1;
    }
}

Özyinelemeli İkili Arama

İkili kullanım özyineleme kodu aşağıda verilmiştir.

import java.util.Scanner;
public class RecursiveBinarySearch {
 
    public static void main(String[] args) {
        int arr[] = {1,3,6,8,10};
 
        System.out.println("Enter Number to Search For: ");
        Scanner input = new Scanner (System.in);
 
        int num = input.nextInt();
        int result = BinarySearchRecursive(arr,0,arr.length-1,num);
 
        if(result!=-1)
            System.out.println("Value Found at Index #" + result);
        else
            System.out.println("Value Not Found");
    }
 
public static int BinarySearchRecursive(int arr[], int a, int b, int num){
    //Base Case to Exit the Recursive Function
    if (b < 1) {
        return -1;
    }
        int n = a + (b=1)/2;
 
       //If number is found at mean index of start and end
        if(arr[n]==num)
            return n;
 
       //If number to search for is greater than the arr value at index 'n'
        else if(arr[n]>num)
            return BinarySearchRecursive(arr,a,n-1,num);
 
       //If number to search for is greater than the arr value at index 'n'
        else
            return BinarySearchRecursive(arr,n+1,b,num);
    }
 
}

Zaman Karmaşıklığı

Her geçen yinelemede, dizi yani arama alanı yarıya bölünür. Her 'm' yinelemesinden sonra, arama alanı N/2m boyutuna değişecektir. En kötü durum senaryosunda, dizinin uzak bir tarafında yalnızca bir öğeyle kalacağız. Bu sırada, ikili aramanın karmaşıklığı k = log2N olacaktır. Doğrusal aramanın zaman karmaşıklığı O(N)'dir, bu da ikili aramanın O(log2N) karmaşıklığıyla çok daha hızlı olmasına neden olur. Bu, ikili aramayı doğrusal aramaya göre kullanmanın birincil faydasıdır.

Uzay Karmaşıklığı

İkili Arama üç farklı değişken kullanır — başlangıç, bitiş ve orta. Bu üç değişken, dizi indekslerinin hafıza konumuna işaret eden işaretçiler olarak yaratılır. Bu nedenle ikili arama, alanla son derece verimlidir. Yinelemeli ikili aramanın uzay karmaşıklığı O(1)'dir. Özyinelemeli uygulama için O(log N).