Hướng dẫn python binary search array - mảng tìm kiếm nhị phân python

Chào ace, bài này chúng ta sẽ tìm hiểu về một trong các thuật toán sắp xếp được sử dụng nhiều trong lập trình và thực tế nhất đó là Binary Search, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, ứng dụng của nó, code ví dụ, điểm mạnh, điểm yếu…) về Binary Search thông qua các phần sau.Binary Search, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, ứng dụng của nó, code ví dụ, điểm mạnh, điểm yếu…) về Binary Search thông qua các phần sau.

• 1. Giới thiệu
• 2. Code ví dụ trên nhiều ngôn ngữ
  • 2.1 Triển khai đệ quy với Tìm kiếm nhị phân(Binary Search)
  • 2.2 Thực hiện lặp đi lặp lại để Tìm kiếm nhị phân(Binary Search)
• 3. Độ phức tạp

Cho một mảng đã sắp xếp arr [] gồm n phần tử, hãy viết một hàm để tìm kiếm một phần tử x đã cho trong arr [].

Một cách tiếp cận đơn giản là thực hiện tìm kiếm tuyến tính(Linear Search), độ phức tạp thời gian của thuật toán trên là O (n). Một cách tiếp cận khác để thực hiện tác vụ tương tự là sử dụng Tìm kiếm nhị phân.Linear Search), độ phức tạp thời gian của thuật toán trên là O (n). Một cách tiếp cận khác để thực hiện tác vụ tương tự là sử dụng Tìm kiếm nhị phân.

Tìm kiếm nhị phân(Binary Search): Tìm kiếm một mảng được sắp xếp bằng cách chia đôi khoảng thời gian tìm kiếm nhiều lần. Bắt đầu với một khoảng bao gồm toàn bộ mảng. Nếu giá trị của key tìm kiếm nhỏ hơn mục ở khoảng giữa, hãy thu hẹp khoảng đó xuống nửa dưới. Nếu không, hãy thu hẹp nó ở nửa trên. Lặp lại kiểm tra cho đến khi giá trị được tìm thấy hoặc khoảng thời gian trống. Tìm kiếm một mảng được sắp xếp bằng cách chia đôi khoảng thời gian tìm kiếm nhiều lần. Bắt đầu với một khoảng bao gồm toàn bộ mảng. Nếu giá trị của key tìm kiếm nhỏ hơn mục ở khoảng giữa, hãy thu hẹp khoảng đó xuống nửa dưới. Nếu không, hãy thu hẹp nó ở nửa trên. Lặp lại kiểm tra cho đến khi giá trị được tìm thấy hoặc khoảng thời gian trống.

Ý tưởng của tìm kiếm nhị phân là sử dụng thông tin mà mảng được sắp xếp và giảm độ phức tạp về thời gian thành O (Log n).

Về cơ bản chúng ta bỏ qua một nửa số phần tử chỉ sau một lần so sánh.

1. So sánh x với phần tử ở giữa.
2. Nếu x khớp với phần tử giữa, chúng ta trả về chỉ số giữa.
3. Ngược lại Nếu x lớn hơn phần tử giữa, thì x chỉ có thể nằm trong nửa mảng con bên phải sau phần tử giữa. Vì vậy, chúng ta tái diễn cho một nửa bên phải.
4. Ngược lại (x nhỏ hơn) lặp lại cho nửa bên trái.

2. Code ví dụ trên nhiều ngôn ngữ

2.1 Triển khai đệ quy với Tìm kiếm nhị phân(Binary Search)

C++

// C++ program to implement recursive Binary Search 
#include  
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; 
} 

2.2 Thực hiện lặp đi lặp lại để Tìm kiếm nhị phân(Binary Search)

// C program to implement recursive Binary Search 
#include  
  
// 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; 
} 

3. Độ phức tạp

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

Python 3

# Python3 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
  
# Driver Code 
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); 
    } 
} 

Cho một mảng đã sắp xếp arr [] gồm n phần tử, hãy viết một hàm để tìm kiếm một phần tử x đã cho trong arr [].

= $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; 
?> 

Một cách tiếp cận đơn giản là thực hiện tìm kiếm tuyến tính(Linear Search), độ phức tạp thời gian của thuật toán trên là O (n). Một cách tiếp cận khác để thực hiện tác vụ tương tự là sử dụng Tìm kiếm nhị phân.

Element is present at index 3

2.2 Thực hiện lặp đi lặp lại để Tìm kiếm nhị phân(Binary Search)

C++

// C++ program to implement recursive Binary Search 
#include  
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; 
} 

2.2 Thực hiện lặp đi lặp lại để Tìm kiếm nhị phân(Binary Search)

// C program to implement iterative Binary Search 
#include  
  
// 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; 
} 

3. Độ phức tạp

// 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 3

// C program to implement recursive Binary Search 
#include  
  
// 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  
  
// 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; 
} 

Cho một mảng đã sắp xếp arr [] gồm n phần tử, hãy viết một hàm để tìm kiếm một phần tử x đã cho trong arr [].

// C program to implement recursive Binary Search 
#include  
  
// 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; 
} 

Một cách tiếp cận đơn giản là thực hiện tìm kiếm tuyến tính(Linear Search), độ phức tạp thời gian của thuật toán trên là O (n). Một cách tiếp cận khác để thực hiện tác vụ tương tự là sử dụng Tìm kiếm nhị phân.

Element is present at index 3

3. Độ phức tạp

Cho một mảng đã sắp xếp arr [] gồm n phần tử, hãy viết một hàm để tìm kiếm một phần tử x đã cho trong arr [].

Một cách tiếp cận đơn giản là thực hiện tìm kiếm tuyến tính(Linear Search), độ phức tạp thời gian của thuật toán trên là O (n). Một cách tiếp cận khác để thực hiện tác vụ tương tự là sử dụng Tìm kiếm nhị phân.

Tìm kiếm nhị phân(Binary Search): Tìm kiếm một mảng được sắp xếp bằng cách chia đôi khoảng thời gian tìm kiếm nhiều lần. Bắt đầu với một khoảng bao gồm toàn bộ mảng. Nếu giá trị của key tìm kiếm nhỏ hơn mục ở khoảng giữa, hãy thu hẹp khoảng đó xuống nửa dưới. Nếu không, hãy thu hẹp nó ở nửa trên. Lặp lại kiểm tra cho đến khi giá trị được tìm thấy hoặc khoảng thời gian trống.

Ý tưởng của tìm kiếm nhị phân là sử dụng thông tin mà mảng được sắp xếp và giảm độ phức tạp về thời gian thành O (Log n).

Về cơ bản chúng ta bỏ qua một nửa số phần tử chỉ sau một lần so sánh. O (1) trong trường hợp thực hiện lặp đi lặp lại. Trong trường hợp thực hiện đệ quy, không gian ngăn xếp gọi đệ quy O (Logn).

So sánh x với phần tử ở giữa.

• w3schools
• Nếu x khớp với phần tử giữa, chúng ta trả về chỉ số giữa.
• Ngược lại Nếu x lớn hơn phần tử giữa, thì x chỉ có thể nằm trong nửa mảng con bên phải sau phần tử giữa. Vì vậy, chúng ta tái diễn cho một nửa bên phải.
• dev.to

Ngược lại (x nhỏ hơn) lặp lại cho nửa bên trái.

• C
• Java
• PHP

Kết quả:

• Thời gian phức tạp:
• Độ phức tạp về thời gian của Tìm kiếm nhị phân có thể được viết là
• T(n) = T(n/2) + c
• Sự lặp lại ở trên có thể được giải quyết bằng cách sử dụng phương pháp đệ quy tree hoặc phương pháp Master. Nó nằm trong trường hợp II của Phương pháp Master và giải pháp của sự tái diễn là

  
  // C program to implement recursive Binary Search 
  #include  
    
  // 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; 
  } 
  

  4 (Logn).
• Không gian phụ trợ: O (1) trong trường hợp thực hiện lặp đi lặp lại. Trong trường hợp thực hiện đệ quy, không gian ngăn xếp gọi đệ quy O (Logn).
• Nguồn và Tài liệu tiếng anh tham khảo:
• Geeksforgeeks
• codechef

Tài liệu từ cafedev:

Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.