Binary Search sa Java: Recursive, Iterative at Java Collections

Ang Linear Search sa Java ay palaging ang go-to na paraan upang makahanap ng elemento sa isang array. Hinahanap nito ang bawat elemento ng array nang sunud-sunod at napakadaling ipatupad. Gayunpaman, ang mga pagkukulang ng Linear Search ay halata kapag ang array na pinag-uusapan ay naglalaman ng libu-libong elemento. Sa ganitong mga kaso, ang pamamaraang "divide and conquer" na ipinatupad ng Binary Search ay mas mahusay at mas mainam para sa mga programmer na nasa isip ang pagiging kumplikado ng oras at espasyo.

Binary Search

Sa Binary Search, ang isang array ay paulit-ulit na nahahati sa dalawang halves hanggang sa makita ang susi (elemento na hinahanap). Ang dibisyon ay virtual ie ang integridad ng data ay pinananatili. Sa bawat pag-ulit, ang gitnang halaga ng array ay nakatuon. Kung ang value ay katumbas ng key na hinahanap namin, ang loop o recursive function ay magwawakas. Kung hindi, ito ay patuloy sa pag-loop. Kung ang gitnang halaga ay mas malaki kaysa sa susi, ang function ay tumutuon sa unang kalahati ng array at vice versa. Ang prosesong ito ay paulit-ulit hanggang sa matagpuan ang susi o ang buong array ay naulit.

Pagkakaiba sa pagitan ng Linear at Binary Search

Binary Search Algorithm

Ang algorithm ng Binary Search ay ibinigay sa ibaba.

1. Tukuyin ang una at huling mga punto ng array. Ang mga puntos ay isasaayos sa bawat pag-ulit ayon sa array at ang susi na hinahanap.
2. Ulitin ang array at ihambing ang gitnang halaga sa pagitan ng iyong kasalukuyang una at huling mga puntos. Sa unang pag-ulit, ang una at ang huling variable ay magiging kapareho ng mga aktwal na nasa array.
3. Kung ang susi ay mas malaki kaysa sa gitnang halaga, ang index ng halagang iyon ay maiimbak sa bagong variable na "Una".
4. Kung ang susi ay mas mababa sa gitnang halaga, ang index ng halagang iyon ay maiimbak sa 'Huling' variable.
5. Ulitin ang kundisyong ito hanggang sa maging totoo ang isa sa dalawang kundisyon:
   • Nahanap ang susi.
   • Ang buong array ay naulit.

Ang code para sa parehong iterative binary search at recursive binary search ay ibinibigay sa ibaba.

Iterative Binary Search

Ang code para sa Binary Search na may umuulit na pamamaraan ay ibinigay sa ibaba.

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;
    }
}

Recursive Binary Search

Ang code para sa Binary gamit ang recursion ay ibinigay sa ibaba.

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);
    }
 
}

Komplikado ng Oras

Sa bawat pagpasa ng pag-ulit, ang array ie ang espasyo sa paghahanap ay nahahati sa kalahati. Pagkatapos ng bawat pag-ulit 'm', ang espasyo sa paghahanap ay magbabago sa laki ng N/2m. Sa pinakamasamang sitwasyon, maiiwan lamang tayo ng isang elemento sa isang malayong bahagi ng array. Sa oras na ito, ang pagiging kumplikado ng binary na paghahanap ay magiging k = log2N. Ang pagiging kumplikado ng oras ng linear na paghahanap ay O(N) na nagreresulta sa pagiging mas mabilis ng binary na paghahanap sa pagiging kumplikado ng O(log2N). Ito ang pangunahing benepisyo ng paggamit ng binary na paghahanap kaysa sa linear na paghahanap.

Pagiging kumplikado ng Space

Gumagamit ang Binary Search ng tatlong magkakaibang variable — simula, wakas at kalagitnaan. Ang tatlong variable na ito ay nilikha bilang mga pointer na tumuturo sa lokasyon ng memorya ng mga indeks ng array. Dahil dito, napakahusay ng paghahanap ng binary sa espasyo. Ang pagiging kumplikado ng espasyo ng iterative binary na paghahanap ay O(1). Para sa recursive na pagpapatupad, ito ay O(log N).