جستجوی دودویی — به زبان ساده

۱۰۴۳۶ بازدید
آخرین به‌روزرسانی: ۱۰ تیر ۱۴۰۲
زمان مطالعه: ۱۰ دقیقه
جستجوی دودویی — به زبان ساده

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

997696

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

در جستجوی دودویی (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

1// C program to implement recursive Binary Search 
2#include <stdio.h> 
3  
4// A recursive binary search function. It returns 
5// location of x in given array arr[l..r] is present, 
6// otherwise -1 
7int binarySearch(int arr[], int l, int r, int x) 
8{ 
9    if (r >= l) { 
10        int mid = l + (r - l) / 2; 
11  
12        // If the element is present at the middle 
13        // itself 
14        if (arr[mid] == x) 
15            return mid; 
16  
17        // If element is smaller than mid, then 
18        // it can only be present in left subarray 
19        if (arr[mid] > x) 
20            return binarySearch(arr, l, mid - 1, x); 
21  
22        // Else the element can only be present 
23        // in right subarray 
24        return binarySearch(arr, mid + 1, r, x); 
25    } 
26  
27    // We reach here when element is not 
28    // present in array 
29    return -1; 
30} 
31  
32int main(void) 
33{ 
34    int arr[] = { 2, 3, 4, 10, 40 }; 
35    int n = sizeof(arr) / sizeof(arr[0]); 
36    int x = 10; 
37    int result = binarySearch(arr, 0, n - 1, x); 
38    (result == -1) ? printf("Element is not present in array") 
39                   : printf("Element is present at index %d", 
40                            result); 
41    return 0; 
42}

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

1// C++ program to implement recursive Binary Search 
2#include <iostream> 
3using namespace std; 
4  
5// A recursive binary search function. It returns 
6// location of x in given array arr[l..r] is present, 
7// otherwise -1 
8int binarySearch(int arr[], int l, int r, int x) 
9{ 
10    if (r >= l) { 
11        int mid = l + (r - l) / 2; 
12  
13        // If the element is present at the middle 
14        // itself 
15        if (arr[mid] == x) 
16            return mid; 
17  
18        // If element is smaller than mid, then 
19        // it can only be present in left subarray 
20        if (arr[mid] > x) 
21            return binarySearch(arr, l, mid - 1, x); 
22  
23        // Else the element can only be present 
24        // in right subarray 
25        return binarySearch(arr, mid + 1, r, x); 
26    } 
27  
28    // We reach here when element is not 
29    // present in array 
30    return -1; 
31} 
32  
33int main(void) 
34{ 
35    int arr[] = { 2, 3, 4, 10, 40 }; 
36    int x = 10; 
37    int n = sizeof(arr) / sizeof(arr[0]); 
38    int result = binarySearch(arr, 0, n - 1, x); 
39    (result == -1) ? cout << "Element is not present in array"
40                   : cout << "Element is present at index " << result; 
41    return 0; 
42}

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

1// Java implementation of recursive Binary Search 
2class BinarySearch { 
3    // Returns index of x if it is present in arr[l.. 
4    // r], else return -1 
5    int binarySearch(int arr[], int l, int r, int x) 
6    { 
7        if (r >= l) { 
8            int mid = l + (r - l) / 2; 
9  
10            // If the element is present at the 
11            // middle itself 
12            if (arr[mid] == x) 
13                return mid; 
14  
15            // If element is smaller than mid, then 
16            // it can only be present in left subarray 
17            if (arr[mid] > x) 
18                return binarySearch(arr, l, mid - 1, x); 
19  
20            // Else the element can only be present 
21            // in right subarray 
22            return binarySearch(arr, mid + 1, r, x); 
23        } 
24  
25        // We reach here when element is not present 
26        // in array 
27        return -1; 
28    } 
29  
30    // Driver method to test above 
31    public static void main(String args[]) 
32    { 
33        BinarySearch ob = new BinarySearch(); 
34        int arr[] = { 2, 3, 4, 10, 40 }; 
35        int n = arr.length; 
36        int x = 10; 
37        int result = ob.binarySearch(arr, 0, n - 1, x); 
38        if (result == -1) 
39            System.out.println("Element not present"); 
40        else
41            System.out.println("Element found at index " + result); 
42    } 
43} 
44/* This code is contributed by Rajat Mishra */

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

1# Python Program for recursive binary search. 
2  
3# Returns index of x in arr if present, else -1 
4def binarySearch (arr, l, r, x): 
5  
6    # Check base case 
7    if r >= l: 
8  
9        mid = l + (r - l)/2
10  
11        # If element is present at the middle itself 
12        if arr[mid] == x: 
13            return mid 
14          
15        # If element is smaller than mid, then it  
16        # can only be present in left subarray 
17        elif arr[mid] > x: 
18            return binarySearch(arr, l, mid-1, x) 
19  
20        # Else the element can only be present  
21        # in right subarray 
22        else: 
23            return binarySearch(arr, mid + 1, r, x) 
24  
25    else: 
26        # Element is not present in the array 
27        return -1
28  
29# Test array 
30arr = [ 2, 3, 4, 10, 40 ] 
31x = 10
32  
33# Function call 
34result = binarySearch(arr, 0, len(arr)-1, x) 
35  
36if result != -1: 
37    print "Element is present at index % d" % result 
38else: 
39    print "Element is not present in array"

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

1// C# implementation of recursive Binary Search 
2using System; 
3  
4class GFG { 
5    // Returns index of x if it is present in 
6    // arr[l..r], else return -1 
7    static int binarySearch(int[] arr, int l, 
8                            int r, int x) 
9    { 
10        if (r >= l) { 
11            int mid = l + (r - l) / 2; 
12  
13            // If the element is present at the 
14            // middle itself 
15            if (arr[mid] == x) 
16                return mid; 
17  
18            // If element is smaller than mid, then 
19            // it can only be present in left subarray 
20            if (arr[mid] > x) 
21                return binarySearch(arr, l, mid - 1, x); 
22  
23            // Else the element can only be present 
24            // in right subarray 
25            return binarySearch(arr, mid + 1, r, x); 
26        } 
27  
28        // We reach here when element is not present 
29        // in array 
30        return -1; 
31    } 
32  
33    // Driver method to test above 
34    public static void Main() 
35    { 
36  
37        int[] arr = { 2, 3, 4, 10, 40 }; 
38        int n = arr.Length; 
39        int x = 10; 
40  
41        int result = binarySearch(arr, 0, n - 1, x); 
42  
43        if (result == -1) 
44            Console.WriteLine("Element not present"); 
45        else
46            Console.WriteLine("Element found at index "
47                              + result); 
48    } 
49} 
50  
51// This code is contributed by Sam007.

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

1<?php 
2// PHP program to implement 
3// recursive Binary Search 
4  
5// A recursive binary search 
6// function. It returns location 
7// of x in given array arr[l..r]  
8// is present, otherwise -1 
9function binarySearch($arr, $l, $r, $x) 
10{ 
11if ($r >= $l) 
12{ 
13        $mid = ceil($l + ($r - $l) / 2); 
14  
15        // If the element is present  
16        // at the middle itself 
17        if ($arr[$mid] == $x)  
18            return floor($mid); 
19  
20        // If element is smaller than  
21        // mid, then it can only be  
22        // present in left subarray 
23        if ($arr[$mid] > $x)  
24            return binarySearch($arr, $l,  
25                                $mid - 1, $x); 
26  
27        // Else the element can only  
28        // be present in right subarray 
29        return binarySearch($arr, $mid + 1,  
30                            $r, $x); 
31} 
32  
33// We reach here when element  
34// is not present in array 
35return -1; 
36} 
37  
38// Driver Code 
39$arr = array(2, 3, 4, 10, 40); 
40$n = count($arr); 
41$x = 10; 
42$result = binarySearch($arr, 0, $n - 1, $x); 
43if(($result == -1)) 
44echo "Element is not present in array"; 
45else
46echo "Element is present at index ", 
47                            $result; 
48                              
49// This code is contributed by anuj_67. 
50?>

خروجی

Element is present at index 3

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

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

1// C program to implement iterative Binary Search 
2#include <stdio.h> 
3  
4// A iterative binary search function. It returns 
5// location of x in given array arr[l..r] if present, 
6// otherwise -1 
7int binarySearch(int arr[], int l, int r, int x) 
8{ 
9    while (l <= r) { 
10        int m = l + (r - l) / 2; 
11  
12        // Check if x is present at mid 
13        if (arr[m] == x) 
14            return m; 
15  
16        // If x greater, ignore left half 
17        if (arr[m] < x) 
18            l = m + 1; 
19  
20        // If x is smaller, ignore right half 
21        else
22            r = m - 1; 
23    } 
24  
25    // if we reach here, then element was 
26    // not present 
27    return -1; 
28} 
29  
30int main(void) 
31{ 
32    int arr[] = { 2, 3, 4, 10, 40 }; 
33    int n = sizeof(arr) / sizeof(arr[0]); 
34    int x = 10; 
35    int result = binarySearch(arr, 0, n - 1, x); 
36    (result == -1) ? printf("Element is not present"
37                            " in array") 
38                   : printf("Element is present at "
39                            "index %d", 
40                            result); 
41    return 0; 
42}

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

1// C++ program to implement recursive Binary Search 
2#include <iostream> 
3using namespace std; 
4  
5// A iterative binary search function. It returns 
6// location of x in given array arr[l..r] if present, 
7// otherwise -1 
8int binarySearch(int arr[], int l, int r, int x) 
9{ 
10    while (l <= r) { 
11        int m = l + (r - l) / 2; 
12  
13        // Check if x is present at mid 
14        if (arr[m] == x) 
15            return m; 
16  
17        // If x greater, ignore left half 
18        if (arr[m] < x) 
19            l = m + 1; 
20  
21        // If x is smaller, ignore right half 
22        else
23            r = m - 1; 
24    } 
25  
26    // if we reach here, then element was 
27    // not present 
28    return -1; 
29} 
30  
31int main(void) 
32{ 
33    int arr[] = { 2, 3, 4, 10, 40 }; 
34    int x = 10; 
35    int n = sizeof(arr) / sizeof(arr[0]); 
36    int result = binarySearch(arr, 0, n - 1, x); 
37    (result == -1) ? cout << "Element is not present in array"
38                   : cout << "Element is present at index " << result; 
39    return 0; 
40}

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

1// Java implementation of iterative Binary Search 
2class BinarySearch { 
3    // Returns index of x if it is present in arr[], 
4    // else return -1 
5    int binarySearch(int arr[], int x) 
6    { 
7        int l = 0, r = arr.length - 1; 
8        while (l <= r) { 
9            int m = l + (r - l) / 2; 
10  
11            // Check if x is present at mid 
12            if (arr[m] == x) 
13                return m; 
14  
15            // If x greater, ignore left half 
16            if (arr[m] < x) 
17                l = m + 1; 
18  
19            // If x is smaller, ignore right half 
20            else
21                r = m - 1; 
22        } 
23  
24        // if we reach here, then element was 
25        // not present 
26        return -1; 
27    } 
28  
29    // Driver method to test above 
30    public static void main(String args[]) 
31    { 
32        BinarySearch ob = new BinarySearch(); 
33        int arr[] = { 2, 3, 4, 10, 40 }; 
34        int n = arr.length; 
35        int x = 10; 
36        int result = ob.binarySearch(arr, x); 
37        if (result == -1) 
38            System.out.println("Element not present"); 
39        else
40            System.out.println("Element found at "
41                               + "index " + result); 
42    } 
43}

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

1# Python code to implement iterative Binary  
2# Search. 
3  
4# It returns location of x in given array arr  
5# if present, else returns -1 
6def binarySearch(arr, l, r, x): 
7  
8    while l <= r: 
9  
10        mid = l + (r - l)/2; 
11          
12        # Check if x is present at mid 
13        if arr[mid] == x: 
14            return mid 
15  
16        # If x is greater, ignore left half 
17        elif arr[mid] < x: 
18            l = mid + 1
19  
20        # If x is smaller, ignore right half 
21        else: 
22            r = mid - 1
23      
24    # If we reach here, then the element 
25    # was not present 
26    return -1
27  
28  
29# Test array 
30arr = [ 2, 3, 4, 10, 40 ] 
31x = 10
32  
33# Function call 
34result = binarySearch(arr, 0, len(arr)-1, x) 
35  
36if result != -1: 
37    print "Element is present at index % d" % result 
38else: 
39    print "Element is not present in array"

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

1// C# implementation of iterative Binary Search 
2using System; 
3  
4class GFG { 
5    // Returns index of x if it is present in arr[], 
6    // else return -1 
7    static int binarySearch(int[] arr, int x) 
8    { 
9        int l = 0, r = arr.Length - 1; 
10        while (l <= r) { 
11            int m = l + (r - l) / 2; 
12  
13            // Check if x is present at mid 
14            if (arr[m] == x) 
15                return m; 
16  
17            // If x greater, ignore left half 
18            if (arr[m] < x) 
19                l = m + 1; 
20  
21            // If x is smaller, ignore right half 
22            else
23                r = m - 1; 
24        } 
25  
26        // if we reach here, then element was 
27        // not present 
28        return -1; 
29    } 
30  
31    // Driver method to test above 
32    public static void Main() 
33    { 
34        int[] arr = { 2, 3, 4, 10, 40 }; 
35        int n = arr.Length; 
36        int x = 10; 
37        int result = binarySearch(arr, x); 
38        if (result == -1) 
39            Console.WriteLine("Element not present"); 
40        else
41            Console.WriteLine("Element found at "
42                              + "index " + result); 
43    } 
44} 
45// This code is contributed by Sam007

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

1<?php 
2// PHP program to implement 
3// iterative Binary Search 
4  
5// A iterative binary search  
6// function. It returns location  
7// of x in given array arr[l..r]  
8// if present, otherwise -1 
9function binarySearch($arr, $l,  
10                      $r, $x) 
11{ 
12    while ($l <= $r) 
13    { 
14        $m = $l + ($r - $l) / 2; 
15  
16        // Check if x is present at mid 
17        if ($arr[$m] == $x) 
18            return floor($m); 
19  
20        // If x greater, ignore 
21        // left half 
22        if ($arr[$m] < $x) 
23            $l = $m + 1; 
24  
25        // If x is smaller,  
26        // ignore right half 
27        else
28            $r = $m - 1; 
29    } 
30  
31    // if we reach here, then  
32    // element was not present 
33    return -1; 
34} 
35  
36// Driver Code 
37$arr = array(2, 3, 4, 10, 40); 
38$n = count($arr); 
39$x = 10; 
40$result = binarySearch($arr, 0,  
41                       $n - 1, $x); 
42if(($result == -1)) 
43echo "Element is not present in array"; 
44else
45echo "Element is present at index ",  
46                            $result; 
47  
48// This code is contributed by anuj_67. 
49?> 

خروجی

Element is present at index 3

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

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

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

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

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

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

^^

بر اساس رای ۲۰ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
نظر شما چیست؟

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