جاوا ۾ بائنري ڳولها: بار بار، ٻيهر ۽ جاوا مجموعا

جاوا ۾ لڪير ڳولا هميشه هڪ صف ۾ هڪ عنصر ڳولڻ لاء وڃڻ وارو طريقو آهي. اهو صف جي هر عنصر کي ترتيب سان ڳولي ٿو ۽ لاڳو ڪرڻ بلڪل آسان آهي. جڏهن ته، لڪير جي ڳولا جي گهٽتائي واضح آهي جڏهن سوال ۾ صف ۾ هزارين عناصر شامل آهن. اهڙين حالتن ۾، "تقسيم ۽ فتح" جو طريقو بائنري سرچ پاران لاڳو ڪيو ويو آهي گهڻو وڌيڪ ڪارائتو ۽ ترجيح آهي پروگرامرز لاءِ ذهن ۾ وقت ۽ جڳهه جي پيچيدگي سان.

بائنري ڳولا

بائنري ڳولها ۾، هڪ صف کي بار بار ٻن حصن ۾ ورهايو ويندو آهي جيستائين ڪنجي (عنصر جيڪو ڳولهيو پيو وڃي) مليو. ڊويزن مجازي آهي يعني ڊيٽا جي سالميت برقرار رکي ٿي. هر ورهاڱي سان، صف جي وچين قدر تي ڌيان ڏنو ويو آهي. جيڪڏهن قدر ان جي برابر آهي جنهن کي اسان ڳولي رهيا آهيون، لوپ يا ٻيهر ورجائيندڙ فنڪشن ختم ٿي ويندو. ٻي صورت ۾، اهو ڦرندو رهي ٿو. جيڪڏهن وچين قدر ڪن کان وڌيڪ آهي، فنڪشن پوءِ صف جي پهرين اڌ تي ڌيان ڏئي ٿو ۽ ان جي برعڪس. اهو عمل بار بار ڪيو ويندو آهي جيستائين ڪنجي مليل هجي يا پوري صف کي ورجايو ويو آهي.

لڪير ۽ بائنري ڳولا جي وچ ۾ فرق

بائنري ڳولا الگورتھم

بائنري ڳولا جو الگورتھم ھيٺ ڏنل آھي.

1. صف جي پهرين ۽ آخري پوائنٽ کي طئي ڪريو. پوائنٽن کي ترتيب ڏني ويندي ھر ھڪ ورجائي تي ترتيب ڏنل صف جي مطابق ۽ چاٻي جي ڳولا ڪئي پئي وڃي.
2. صف جي ذريعي ٻيهر ورجايو ۽ توهان جي موجوده پهرين ۽ آخري پوائنٽن جي وچ ۾ وچولي قدر جو موازنہ ڪريو. پهرين ورهاڱي ۾، پهريون ۽ آخري متغير ساڳيو ئي هوندو جيئن اصل ۾ صف ۾.
3. جيڪڏهن ڪنجي وچولي قدر کان وڌيڪ آهي، ته ان قيمت جو انڊيڪس نئين "پهرين" متغير ۾ محفوظ ڪيو ويندو.
4. جيڪڏهن ڪنجي وچولي قدر کان گهٽ آهي، ته ان قيمت جي انڊيڪس کي 'آخري' متغير ۾ محفوظ ڪيو ويندو.
5. اها حالت ورجائي ويندي آهي جيستائين ٻن شرطن مان هڪ صحيح ٿي وڃي:
   • چاٻي ملي آهي.
   • سڄو سلسلو ورجايو ويو آهي.

ٻنھي لاءِ بار بار واري بائنري ڳولھا ۽ ريسرسيو بائنري ڳولھا لاءِ ڪوڊ ھيٺ ڏنل آھي.

تکراري بائنري ڳولا

بائنري ڳولها لاءِ ڪوڊ هڪ تکراري طريقي سان هيٺ ڏنل آهي.

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

ٻيهر ورجائيندڙ بائنري ڳولا

recursion استعمال ڪندي بائنري لاءِ ڪوڊ ھيٺ ڏنل آھي.

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

}

وقت جي پيچيدگي

هر گذرڻ واري ورجائي سان، صف يعني ڳولا واري جاءِ اڌ ۾ ورهائجي ويندي آهي. هر ورجائي 'm' کان پوء، ڳولا جي جاء تبديل ٿي ويندي N/2m جي سائيز ۾. بدترين صورت حال ۾، اسان صرف هڪ عنصر سان صف جي هڪ پري پاسي تي ڇڏي ويندي. هن وقت، بائنري ڳولا جي پيچيدگي k = log2N هوندي. لڪير جي ڳولا جي وقت جي پيچيدگي O (N) آهي جنهن جي نتيجي ۾ بائنري ڳولا O (log2N) پيچيدگي سان تمام تيز آهي. اهو بنيادي فائدو آهي بائنري ڳولها استعمال ڪرڻ جو لڪير ڳولا تي.

خلائي پيچيدگي

بائنري ڳولها ٽي مختلف متغير استعمال ڪري ٿي - شروعات، آخر ۽ وچ. اهي ٽي متغير ٺاهيا ويا آهن پوائنٽر جي طور تي جيڪي اشارو ڪن ٿا ميموري مقام جي سرن جي اشارن جي. انهي جي ڪري، بائنري ڳولا خلا سان انتهائي موثر آهي. ٻيھري بائنري ڳولا جي خلائي پيچيدگي O(1) آھي. بار بار لاڳو ڪرڻ لاء، اهو O (log N) آهي.