در این مطلب، الگوریتم جستجوی دودویی (Binary Search) مورد بررسی قرار گرفته و پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون انجام شده است.

جستجوی دودویی

در جستجوی دودویی (Binary Search)‌، جستجو در یک آرایه مرتب شده، با تقسیم تکرار شونده بازه جستجو به نصف، انجام می‌شود. کار با بازه‌ای که کل آرایه را پوشش می‌دهد، آغاز می‌شود. اگر مقدار کلید جستجو برابر با عنصر میانی باشد، اندیس آن بازگردانده می‌شود. در غیر این صورت، اگر مقدار کلید جستجو کمتر از عنصری باشد که در میانه بازه قرار دارد، بازه شکسته شده و جستجو در نیمه کمتر ادامه پیدا می‌کند. در صورتی که مقدار کلید جستجو بزرگ‌تر از اندیس میانی آرایه باشد، جستجو در نیمه بیشتر (حاوی مقادیر بزرگ‌تر) آرایه ادامه پیدا می‌کند. کار شکستن آرایه به دو نیم و انتخاب نیمه‌ای که جستجو باید در آن انجام شود، مکررا و تا هنگامی که عنصر مورد نظر در آرایه یافته شود و یا مشخص شود که عنصر مورد نظر در آرایه وجود ندارد، ادامه خواهد داشت.

مثالی از جستجوی دودویی

آرایه مرتب شده []arr شامل n عنصر موجود است. هدف، نوشتن تابعی است که یک عنصر داده شده x را در آرایه مذکور ([]arr) جستجو کند. یک رویکرد ساده برای انجام این کار، استفاده از «جستجوی خطی» (Linear Search) است. پیچیدگی زمانی الگوریتم جستجوی خطی، (O(n است. رویکرد دیگر، انجام کار مشابهی با استفاده از «جستجوی دودویی» (Binary Search) است. ایده اصلی نهفته در پس جستجوی دودویی، استفاده از اطلاعات موجود در آرایه مرتب شده و کاهش پیچیدگی زمانی به (O(Log n است. در جستجوی دودویی اساسا نیمی از عناصر تنها پس از یک مقایسه حذف می‌شوند. برای انجام جستجو، از الگوریتم زیر استفاده می‌شود.

  1. x با عنصر میانی آرایه مقایسه می‌شود.
  2. اگر x با عنصر میانی آرایه یکی بود، اندیس عنصر میانی را بازگردان.
  3. در غیر این صورت، اگر x بزرگ‌تر از عنصر میانی بود، امکان دارد x در نیمه سمت راست آرایه، پس از عنصر میانی، قرار داشته باشد (شایان توجه است که همانطور که پیش‌تر اشاره شد، آرایه مرتب شده است. پس در این حالت، نیمه‌ای با مقادیر بزرگ‌تر برای ادامه جستجو گزینش می‌شود).
  4. در غیر این صورت، اگر x از عنصر میانی آرایه کوچک‌تر باشد، آرایه به دو نیمه شکسته شده و جستجو در نیمه سمت چپ (با مقادیر کوچک‌تر از میانه)، ادامه پیدا می‌کند.

جستجوی دودویی

در ادامه، پیاده‌سازی الگوریتم جستجوی دودویی به صورت بازگشتی، در زبان‌های برنامه‌نویسی C++ ،C، «جاوا» (Java)، «پایتون» (Python)، «سی‌شارپ» (#C) و PHP ارائه شده است.

کد بازگشتی الگوریتم جستجوی دودویی در C

// C program to implement recursive Binary Search 
#include <stdio.h> 
  
// A recursive binary search function. It returns 
// location of x in given array arr[l..r] is present, 
// otherwise -1 
int binarySearch(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 
  
        // If the element is present at the middle 
        // itself 
        if (arr[mid] == x) 
            return mid; 
  
        // If element is smaller than mid, then 
        // it can only be present in left subarray 
        if (arr[mid] > x) 
            return binarySearch(arr, l, mid - 1, x); 
  
        // Else the element can only be present 
        // in right subarray 
        return binarySearch(arr, mid + 1, r, x); 
    } 
  
    // We reach here when element is not 
    // present in array 
    return -1; 
} 
  
int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int x = 10; 
    int result = binarySearch(arr, 0, n - 1, x); 
    (result == -1) ? printf("Element is not present in array") 
                   : printf("Element is present at index %d", 
                            result); 
    return 0; 
}

کد بازگشتی الگوریتم جستجوی دودویی در ++C

// C++ program to implement recursive Binary Search 
#include <iostream> 
using namespace std; 
  
// A recursive binary search function. It returns 
// location of x in given array arr[l..r] is present, 
// otherwise -1 
int binarySearch(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 
  
        // If the element is present at the middle 
        // itself 
        if (arr[mid] == x) 
            return mid; 
  
        // If element is smaller than mid, then 
        // it can only be present in left subarray 
        if (arr[mid] > x) 
            return binarySearch(arr, l, mid - 1, x); 
  
        // Else the element can only be present 
        // in right subarray 
        return binarySearch(arr, mid + 1, r, x); 
    } 
  
    // We reach here when element is not 
    // present in array 
    return -1; 
} 
  
int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 }; 
    int x = 10; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int result = binarySearch(arr, 0, n - 1, x); 
    (result == -1) ? cout << "Element is not present in array"
                   : cout << "Element is present at index " << result; 
    return 0; 
}

کد بازگشتی الگوریتم جستجوی دودویی در جاوا

// Java implementation of recursive Binary Search 
class BinarySearch { 
    // Returns index of x if it is present in arr[l.. 
    // r], else return -1 
    int binarySearch(int arr[], int l, int r, int x) 
    { 
        if (r >= l) { 
            int mid = l + (r - l) / 2; 
  
            // If the element is present at the 
            // middle itself 
            if (arr[mid] == x) 
                return mid; 
  
            // If element is smaller than mid, then 
            // it can only be present in left subarray 
            if (arr[mid] > x) 
                return binarySearch(arr, l, mid - 1, x); 
  
            // Else the element can only be present 
            // in right subarray 
            return binarySearch(arr, mid + 1, r, x); 
        } 
  
        // We reach here when element is not present 
        // in array 
        return -1; 
    } 
  
    // Driver method to test above 
    public static void main(String args[]) 
    { 
        BinarySearch ob = new BinarySearch(); 
        int arr[] = { 2, 3, 4, 10, 40 }; 
        int n = arr.length; 
        int x = 10; 
        int result = ob.binarySearch(arr, 0, n - 1, x); 
        if (result == -1) 
            System.out.println("Element not present"); 
        else
            System.out.println("Element found at index " + result); 
    } 
} 
/* This code is contributed by Rajat Mishra */

کد بازگشتی الگوریتم جستجوی دودویی در پایتون

# Python Program for recursive binary search. 
  
# Returns index of x in arr if present, else -1 
def binarySearch (arr, l, r, x): 
  
    # Check base case 
    if r >= l: 
  
        mid = l + (r - l)/2
  
        # If element is present at the middle itself 
        if arr[mid] == x: 
            return mid 
          
        # If element is smaller than mid, then it  
        # can only be present in left subarray 
        elif arr[mid] > x: 
            return binarySearch(arr, l, mid-1, x) 
  
        # Else the element can only be present  
        # in right subarray 
        else: 
            return binarySearch(arr, mid + 1, r, x) 
  
    else: 
        # Element is not present in the array 
        return -1
  
# Test array 
arr = [ 2, 3, 4, 10, 40 ] 
x = 10
  
# Function call 
result = binarySearch(arr, 0, len(arr)-1, x) 
  
if result != -1: 
    print "Element is present at index % d" % result 
else: 
    print "Element is not present in array"

کد بازگشتی الگوریتم جستجوی دودویی در #C

// C# implementation of recursive Binary Search 
using System; 
  
class GFG { 
    // Returns index of x if it is present in 
    // arr[l..r], else return -1 
    static int binarySearch(int[] arr, int l, 
                            int r, int x) 
    { 
        if (r >= l) { 
            int mid = l + (r - l) / 2; 
  
            // If the element is present at the 
            // middle itself 
            if (arr[mid] == x) 
                return mid; 
  
            // If element is smaller than mid, then 
            // it can only be present in left subarray 
            if (arr[mid] > x) 
                return binarySearch(arr, l, mid - 1, x); 
  
            // Else the element can only be present 
            // in right subarray 
            return binarySearch(arr, mid + 1, r, x); 
        } 
  
        // We reach here when element is not present 
        // in array 
        return -1; 
    } 
  
    // Driver method to test above 
    public static void Main() 
    { 
  
        int[] arr = { 2, 3, 4, 10, 40 }; 
        int n = arr.Length; 
        int x = 10; 
  
        int result = binarySearch(arr, 0, n - 1, x); 
  
        if (result == -1) 
            Console.WriteLine("Element not present"); 
        else
            Console.WriteLine("Element found at index "
                              + result); 
    } 
} 
  
// This code is contributed by Sam007.

کد بازگشتی الگوریتم جستجوی دودویی در PHP

<?php 
// PHP program to implement 
// recursive Binary Search 
  
// A recursive binary search 
// function. It returns location 
// of x in given array arr[l..r]  
// is present, otherwise -1 
function binarySearch($arr, $l, $r, $x) 
{ 
if ($r >= $l) 
{ 
        $mid = ceil($l + ($r - $l) / 2); 
  
        // If the element is present  
        // at the middle itself 
        if ($arr[$mid] == $x)  
            return floor($mid); 
  
        // If element is smaller than  
        // mid, then it can only be  
        // present in left subarray 
        if ($arr[$mid] > $x)  
            return binarySearch($arr, $l,  
                                $mid - 1, $x); 
  
        // Else the element can only  
        // be present in right subarray 
        return binarySearch($arr, $mid + 1,  
                            $r, $x); 
} 
  
// We reach here when element  
// is not present in array 
return -1; 
} 
  
// Driver Code 
$arr = array(2, 3, 4, 10, 40); 
$n = count($arr); 
$x = 10; 
$result = binarySearch($arr, 0, $n - 1, $x); 
if(($result == -1)) 
echo "Element is not present in array"; 
else
echo "Element is present at index ", 
                            $result; 
                              
// This code is contributed by anuj_67. 
?>

خروجی

Element is present at index 3

در ادامه، کد مربوط به پیاده‌سازی الگوریتم جستجوی دودویی به صورت «تکرار شونده» (Iterative) ارائه شده است.

کد تکرار شونده الگوریتم جستجوی دودویی در C

// C program to implement iterative Binary Search 
#include <stdio.h> 
  
// A iterative binary search function. It returns 
// location of x in given array arr[l..r] if present, 
// otherwise -1 
int binarySearch(int arr[], int l, int r, int x) 
{ 
    while (l <= r) { 
        int m = l + (r - l) / 2; 
  
        // Check if x is present at mid 
        if (arr[m] == x) 
            return m; 
  
        // If x greater, ignore left half 
        if (arr[m] < x) 
            l = m + 1; 
  
        // If x is smaller, ignore right half 
        else
            r = m - 1; 
    } 
  
    // if we reach here, then element was 
    // not present 
    return -1; 
} 
  
int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int x = 10; 
    int result = binarySearch(arr, 0, n - 1, x); 
    (result == -1) ? printf("Element is not present"
                            " in array") 
                   : printf("Element is present at "
                            "index %d", 
                            result); 
    return 0; 
}

کد تکرار شونده الگوریتم جستجوی دودویی در ++C

// C++ program to implement recursive Binary Search 
#include <iostream> 
using namespace std; 
  
// A iterative binary search function. It returns 
// location of x in given array arr[l..r] if present, 
// otherwise -1 
int binarySearch(int arr[], int l, int r, int x) 
{ 
    while (l <= r) { 
        int m = l + (r - l) / 2; 
  
        // Check if x is present at mid 
        if (arr[m] == x) 
            return m; 
  
        // If x greater, ignore left half 
        if (arr[m] < x) 
            l = m + 1; 
  
        // If x is smaller, ignore right half 
        else
            r = m - 1; 
    } 
  
    // if we reach here, then element was 
    // not present 
    return -1; 
} 
  
int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 }; 
    int x = 10; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int result = binarySearch(arr, 0, n - 1, x); 
    (result == -1) ? cout << "Element is not present in array"
                   : cout << "Element is present at index " << result; 
    return 0; 
}

کد تکرار شونده الگوریتم جستجوی دودویی در جاوا

// Java implementation of iterative Binary Search 
class BinarySearch { 
    // Returns index of x if it is present in arr[], 
    // else return -1 
    int binarySearch(int arr[], int x) 
    { 
        int l = 0, r = arr.length - 1; 
        while (l <= r) { 
            int m = l + (r - l) / 2; 
  
            // Check if x is present at mid 
            if (arr[m] == x) 
                return m; 
  
            // If x greater, ignore left half 
            if (arr[m] < x) 
                l = m + 1; 
  
            // If x is smaller, ignore right half 
            else
                r = m - 1; 
        } 
  
        // if we reach here, then element was 
        // not present 
        return -1; 
    } 
  
    // Driver method to test above 
    public static void main(String args[]) 
    { 
        BinarySearch ob = new BinarySearch(); 
        int arr[] = { 2, 3, 4, 10, 40 }; 
        int n = arr.length; 
        int x = 10; 
        int result = ob.binarySearch(arr, x); 
        if (result == -1) 
            System.out.println("Element not present"); 
        else
            System.out.println("Element found at "
                               + "index " + result); 
    } 
}

کد تکرار شونده الگوریتم جستجوی دودویی در پایتون

# Python code to implement iterative Binary  
# Search. 
  
# It returns location of x in given array arr  
# if present, else returns -1 
def binarySearch(arr, l, r, x): 
  
    while l <= r: 
  
        mid = l + (r - l)/2; 
          
        # Check if x is present at mid 
        if arr[mid] == x: 
            return mid 
  
        # If x is greater, ignore left half 
        elif arr[mid] < x: 
            l = mid + 1
  
        # If x is smaller, ignore right half 
        else: 
            r = mid - 1
      
    # If we reach here, then the element 
    # was not present 
    return -1
  
  
# Test array 
arr = [ 2, 3, 4, 10, 40 ] 
x = 10
  
# Function call 
result = binarySearch(arr, 0, len(arr)-1, x) 
  
if result != -1: 
    print "Element is present at index % d" % result 
else: 
    print "Element is not present in array"

کد تکرار شونده الگوریتم جستجوی دودویی در #C

// C# implementation of iterative Binary Search 
using System; 
  
class GFG { 
    // Returns index of x if it is present in arr[], 
    // else return -1 
    static int binarySearch(int[] arr, int x) 
    { 
        int l = 0, r = arr.Length - 1; 
        while (l <= r) { 
            int m = l + (r - l) / 2; 
  
            // Check if x is present at mid 
            if (arr[m] == x) 
                return m; 
  
            // If x greater, ignore left half 
            if (arr[m] < x) 
                l = m + 1; 
  
            // If x is smaller, ignore right half 
            else
                r = m - 1; 
        } 
  
        // if we reach here, then element was 
        // not present 
        return -1; 
    } 
  
    // Driver method to test above 
    public static void Main() 
    { 
        int[] arr = { 2, 3, 4, 10, 40 }; 
        int n = arr.Length; 
        int x = 10; 
        int result = binarySearch(arr, x); 
        if (result == -1) 
            Console.WriteLine("Element not present"); 
        else
            Console.WriteLine("Element found at "
                              + "index " + result); 
    } 
} 
// This code is contributed by Sam007

کد تکرار شونده الگوریتم جستجوی دودویی در PHP

<?php 
// PHP program to implement 
// iterative Binary Search 
  
// A iterative binary search  
// function. It returns location  
// of x in given array arr[l..r]  
// if present, otherwise -1 
function binarySearch($arr, $l,  
                      $r, $x) 
{ 
    while ($l <= $r) 
    { 
        $m = $l + ($r - $l) / 2; 
  
        // Check if x is present at mid 
        if ($arr[$m] == $x) 
            return floor($m); 
  
        // If x greater, ignore 
        // left half 
        if ($arr[$m] < $x) 
            $l = $m + 1; 
  
        // If x is smaller,  
        // ignore right half 
        else
            $r = $m - 1; 
    } 
  
    // if we reach here, then  
    // element was not present 
    return -1; 
} 
  
// Driver Code 
$arr = array(2, 3, 4, 10, 40); 
$n = count($arr); 
$x = 10; 
$result = binarySearch($arr, 0,  
                       $n - 1, $x); 
if(($result == -1)) 
echo "Element is not present in array"; 
else
echo "Element is present at index ",  
                            $result; 
  
// This code is contributed by anuj_67. 
?> 

خروجی

Element is present at index 3

پیچیدگی زمانی

پیچیدگی زمانی جستجوی دودویی را می‌توان به صورت زیر نوشت:

T(n) = T(n/2) + c

رابطه بازگشتی بالا را می‌توان با استفاده از روش «درخت بازگشتی» (Recursive tree) یا «قضیه اصلی واکاوی (تحلیل) الگوریتم‌ها» (Master method) حل کرد. این رابطه، در حالت دوم قضیه اصلی تحلیل الگوریتم‌ها صدق می‌کند و راهکار بازگشتی به صورت (Theta(Logn است.

«فضای کمکی» (Auxiliary Space)، اگر پیاده‌سازی به صورت تکرار شونده باشد برابر با  (O(1 و در صورتی که بازگشتی باشد، از مرتبه (O(Logn فضای پشته فراخوانی بازگشتی است.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای 13 نفر
آیا این مطلب برای شما مفید بود؟
شما قبلا رای داده‌اید!
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.

«الهام حصارکی»، فارغ‌التحصیل مقطع کارشناسی ارشد مهندسی فناوری اطلاعات، گرایش سیستم‌های اطلاعات مدیریت است. او در زمینه هوش مصنوعی و داده‌کاوی، به ویژه تحلیل شبکه‌های اجتماعی، فعالیت می‌کند.

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *