جاوا میں بائنری تلاش: تکراری، تکراری اور جاوا مجموعہ

جاوا میں لکیری تلاش ہمیشہ سے ایک صف میں عنصر کو تلاش کرنے کا طریقہ رہا ہے۔ یہ صف کے ہر عنصر کو ترتیب وار تلاش کرتا ہے اور اسے نافذ کرنا انتہائی آسان ہے۔ تاہم، لکیری تلاش کی خامیاں اس وقت واضح ہوتی ہیں جب زیر بحث صف میں دسیوں ہزار عناصر ہوتے ہیں۔ ایسے معاملات میں، بائنری سرچ کے ذریعے لاگو "تقسیم اور فتح" کا طریقہ وقت اور جگہ کی پیچیدگی کو ذہن میں رکھتے ہوئے پروگرامرز کے لیے بہت زیادہ موثر اور افضل ہے۔

بائنری تلاش

بائنری سرچ میں، ایک صف کو بار بار دو حصوں میں تقسیم کیا جاتا ہے جب تک کہ کلید (جو عنصر تلاش کیا جا رہا ہے) نہ مل جائے۔ تقسیم ورچوئل ہے یعنی ڈیٹا کی سالمیت برقرار ہے۔ ہر تکرار کے ساتھ، صف کی درمیانی قدر مرکوز ہوتی ہے۔ اگر قیمت اس کلید کے برابر ہے جس کی ہم تلاش کر رہے ہیں، تو لوپ یا تکراری فنکشن ختم ہو جاتا ہے۔ دوسری صورت میں، یہ لوپ پر رہتا ہے. اگر درمیانی قدر کلید سے زیادہ ہے، تو فنکشن صف کے پہلے نصف پر توجہ مرکوز کرتا ہے اور اس کے برعکس۔ یہ عمل اس وقت تک دہرایا جاتا ہے جب تک کہ کلید نہ مل جائے یا پوری صف کو دہرایا گیا ہو۔

لکیری اور بائنری تلاش کے درمیان فرق

بائنری تلاش الگورتھم

بائنری سرچ کا الگورتھم ذیل میں دیا گیا ہے۔

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

تکراری بائنری تلاش

تکرار کا استعمال کرتے ہوئے بائنری کا کوڈ ذیل میں دیا گیا ہے۔

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) ہے۔