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]
Nội dung chính
1. Giới thiệu
Cho một mảng sắp xếp arr [] bao gồm n phần tử, hãy viết một hàm để tìm kiếm một phần tử x đã chọn trong mảng []
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 O [n]. Một cách tiếp cận khác để thực hiện các nhiệm vụ tương tự là sử dụng Tìm kiếm nhị phân tìm kiếm
Tìm kiếm nhị phân phân[Binary Search]. Tìm kiếm một mảng được sắp xếp theo 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 khóa tìm kiếm tìm kiếm nhỏ hơn mục ở khoảng giữa, hãy kéo theo khoảng đó xuống nửa bên dưới. Nếu không, hãy kéo 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 việc tìm kiếm nhị phân tìm kiếm 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
- So sánh x với phần tử ở giữa
- Nếu x khớp với phần tử giữa, chúng ta sẽ 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
- Ngược lại [x nhỏ hơn] lặp lại cho nửa bên trái
2. Ví dụ mã trên nhiều ngôn ngữ
2. 1 Triển khai đệ quy với Tìm kiếm nhị phân [Tìm kiếm nhị phân]
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 = 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];
}
} Trăn 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
Kết quả
Element is present at index 32. 2 Thực hiện vòng lặp lại để tìm kiếm nhị phân tìm kiếm [Tìm kiếm nhị phân]
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 = 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;
}
Kết quả
Element is present at index 33. Độ phức tạp
Phức tạp thời gian
Độ phức tạp về thời gian của Tìm kiếm nhị phân phân tích có thể được viết là
T[n] = T[n/2] + c
Sự cố lặp lại ở trên có thể được giải quyết bằng cách sử dụng cây phương pháp đệ quy 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;
}
Không hỗ trợ khoảng thời gian. O [1] in an Case to the repeat off. 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
- Geekforgeek
- đầu bếp viết mã
- nhà phát triển. đến
Tài liệu từ cafedev
- Full series tự học Cấu hình 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 hình dữ liệu và giải thuật tại đây
- Các chuỗi tự học lập trình khác nhau
Nếu 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