Hướng dẫn binary search python list

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.

• 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.

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.

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 <bits/stdc++.h> 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; }

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

Java

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

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

Kết quả:

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 <bits/stdc++.h> 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; }

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

Java

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

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

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

Kết quả:

Element is present at index 3

3. Độ phức tạp

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à θ (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:

• w3schools
• Geeksforgeeks
• codechef
• dev.to

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.
• Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
• Các series tự học lập trình khác

Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:

• Group Facebook
• Fanpage
• Youtube
• Instagram
• Twitter
• Linkedin
• Pinterest
• Trang chủ

Chào thân ái và quyết thắng!

Đăng ký kênh youtube để ủng hộ Cafedev nha các bạn, Thanks you!