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

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}

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"

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.

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?>

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}

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"

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

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?>