Tìm kiếm nhị phân là một thuật toán tìm kiếm được sử dụng để tìm vị trí của một phần tử (giá trị đích) trong một mảng được sắp xếp. Mảng phải được sắp xếp trước khi áp dụng tìm kiếm nhị phân Show
Tìm kiếm nhị phân còn được gọi bằng các tên này, tìm kiếm logarit, tìm kiếm nhị phân, tìm kiếm nửa khoảng Làm việcThuật toán tìm kiếm nhị phân hoạt động bằng cách so sánh phần tử cần tìm với phần tử ở giữa của mảng và dựa trên sự so sánh này thực hiện theo quy trình bắt buộc Trường hợp 1 - phần tử = giữa, phần tử được tìm thấy trả về chỉ mục Trường hợp 2 − phần tử > giữa, tìm kiếm phần tử trong mảng con bắt đầu từ chỉ số giữa+1 đến n Trường hợp 3 − phần tử < giữa, tìm kiếm phần tử trong mảng con bắt đầu từ chỉ số 0 đến giữa -1 THUẬT TOÁNTham số inital_value , end_value Step 1 : Find the middle element of array. using , middle = initial_value + end_value / 2 ; Step 2 : If middle = element, return ‘element found’ and index. Step 3 : if middle > element, call the function with end_value = middle - 1 . Step 4 : if middle < element, call the function with start_value = middle + 1 . Step 5 : exit. Việc triển khai hàm thuật toán tìm kiếm nhị phân sử dụng lệnh gọi hàm lặp đi lặp lại. Cuộc gọi này có thể có hai loại - Tìm kiếm nhị phân là một thuật toán tìm kiếm nhanh với độ phức tạp trong thời gian chạy là Ο(log n). Thuật toán tìm kiếm này hoạt động theo nguyên tắc chia để trị. Để thuật toán này hoạt động bình thường, việc thu thập dữ liệu phải ở dạng được sắp xếp Tìm kiếm nhị phân tìm kiếm một mục cụ thể bằng cách so sánh mục ở giữa nhất của bộ sưu tập. Nếu khớp xảy ra, thì chỉ mục của mục được trả về. Nếu mục ở giữa lớn hơn mục, thì mục đó được tìm kiếm trong mảng con bên trái của mục ở giữa. Mặt khác, mục được tìm kiếm trong mảng phụ ở bên phải của mục ở giữa. Quá trình này cũng tiếp tục trên mảng con cho đến khi kích thước của mảng con giảm xuống 0 Tìm kiếm nhị phân hoạt động như thế nào?Để tìm kiếm nhị phân hoạt động, bắt buộc phải sắp xếp mảng mục tiêu. Chúng ta sẽ tìm hiểu quá trình tìm kiếm nhị phân với một ví dụ bằng hình ảnh. Sau đây là mảng đã sắp xếp của chúng ta và giả sử rằng chúng ta cần tìm kiếm vị trí của giá trị 31 bằng tìm kiếm nhị phân  Đầu tiên, chúng ta sẽ xác định một nửa mảng bằng cách sử dụng công thức này - mid = low + (high - low) / 2 Đây là, 0 + (9 - 0 ) / 2 = 4 (giá trị nguyên của 4. 5). Vì vậy, 4 là giữa của mảng Bây giờ chúng ta so sánh giá trị được lưu trữ tại vị trí 4, với giá trị được tìm kiếm, tôi. e. 31. Chúng tôi thấy rằng giá trị tại vị trí 4 là 27, không khớp. Vì giá trị lớn hơn 27 và chúng tôi có một mảng được sắp xếp, vì vậy chúng tôi cũng biết rằng giá trị đích phải nằm ở phần trên của mảng Chúng tôi thay đổi mức thấp thành mức trung bình + 1 và tìm lại giá trị mức trung bình mới low = mid + 1 mid = low + (high - low) / 2 Mid mới của chúng tôi bây giờ là 7. Chúng tôi so sánh giá trị được lưu trữ tại vị trí 7 với giá trị mục tiêu của chúng tôi 31 Giá trị được lưu trữ tại vị trí 7 không khớp, thay vào đó, nó nhiều hơn những gì chúng tôi đang tìm kiếm. Vì vậy, giá trị phải ở phần dưới từ vị trí này Do đó, chúng tôi tính toán lại giữa. Lần này là 5 Chúng tôi so sánh giá trị được lưu trữ tại vị trí 5 với giá trị mục tiêu của chúng tôi. Chúng tôi thấy rằng đó là một trận đấu Chúng tôi kết luận rằng giá trị mục tiêu 31 được lưu trữ tại vị trí 5 Tìm kiếm nhị phân giảm một nửa các mục có thể tìm kiếm và do đó làm giảm số lần so sánh được thực hiện với số lượng rất ít Tìm kiếm nhị phân là một thuật toán đơn giản nhằm tìm vị trí của một mục được lưu trữ trong danh sách được sắp xếp. Có một vài biến thể đối với tìm kiếm nhị phân trong chương trình C, chẳng hạn như kiểm tra sự bằng và nhỏ hơn ở mỗi bước của thuật toán Tìm kiếm nhị phân trong C là một ví dụ về quy trình đơn giản có thể được sử dụng để giải quyết các vấn đề phức tạp. Như vậy, đây là một khái niệm cơ bản quan trọng mà bạn sẽ tìm thấy trong hầu hết các cuốn sách hay về ngôn ngữ lập trình C. Trước khi cung cấp cho bạn mã để thiết lập tìm kiếm nhị phân trong C, trước tiên hãy hiểu thuật toán hoạt động chính xác như thế nào Làm thế nào nó hoạt động?Thuật toán tìm kiếm nhị phân áp dụng cho mảng đã sắp xếp để tìm kiếm một phần tử. Việc tìm kiếm bắt đầu bằng việc so sánh phần tử đích với phần tử ở giữa của mảng. Nếu giá trị khớp thì vị trí của phần tử được trả về Trong trường hợp phần tử đích nhỏ hơn phần tử ở giữa (xét mảng theo thứ tự tăng dần) của mảng thì nửa sau của mảng bị loại bỏ và tiếp tục tìm kiếm bằng cách chia nửa đầu Quá trình này giống như khi phần tử đích lớn hơn phần tử ở giữa, chỉ trong trường hợp này, nửa đầu của mảng bị loại bỏ trước khi tiếp tục tìm kiếm. Quá trình lặp lại cho đến khi tìm thấy kết quả khớp cho phần tử đích Đoạn mã sau thực hiện tìm kiếm nhị phân trong ngôn ngữ lập trình C. Mặc dù nó chỉ có thể được sử dụng cho các mảng được sắp xếp, nhưng nó nhanh hơn so với tìm kiếm tuyến tính Nếu các yêu cầu yêu cầu sử dụng tìm kiếm nhị phân trên một mảng chưa được sắp xếp, thì nó cần được sắp xếp trước khi sử dụng thuật toán tìm kiếm nhị phân trên đó. Để làm như vậy, bạn có thể sử dụng một số kỹ thuật sắp xếp, chẳng hạn như sắp xếp bong bóng hoặc sắp xếp hợp nhất GHI CHÚ. - Đoạn mã được đề cập dưới đây giả định rằng các số đầu vào tuân theo thứ tự tăng dần Đây là mã cho Tìm kiếm nhị phân trong C #include
int main()
{
int c, first, last, middle, n, search, array[100];
printf("Enter number of elements:\n");
scanf("%d",&n);
printf("Enter %d integers:\n", n);
for (c = 0; c < n; c++)
scanf("%d",&array[c]);
printf("Enter the value to find:\n");
scanf("%d", &search);
first = 0;
last = n - 1;
middle = (first+last)/2;
while (first <= last) {
if (array[middle] < search)
first = middle + 1;
else if (array[middle] == search) {
printf("%d is present at index %d.\n", search, middle+1);
break;
}
else
last = middle - 1;
middle = (first + last)/2;
}
if (first > last)
printf("Not found! %d is not present in the list.\n", search);
return 0;
}
Đầu ra mẫu Nhập số phần tử 5 Nhập 5 số nguyên 1 Nhập giá trị cần tìm 24 24 có mặt tại chỉ số 4 Các ví dụ khác về triển khai tìm kiếm nhị phân trong chương trình C
GHI CHÚ. - Chương trình này không cho phép bạn nhập các phần tử vì danh sách đã được cài đặt sẵn trong đó. Chương trình chỉ minh họa cách thức hoạt động của tìm kiếm nhị phân trong chương trình C #include
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
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("The element is not present in array")
: printf("The element is present at index %d",
result);
return 0;
}
đầu ra Phần tử có mặt tại chỉ số 3
GHI CHÚ. - Chương trình này không cho phép bạn nhập các phần tử vì danh sách đã được cài đặt sẵn trong đó. Chương trình chỉ minh họa cách thức hoạt động của tìm kiếm nhị phân trong chương trình C #include
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == x)
return m;
if (arr[m] < x)
l = m + 1;
else
r = m - 1;
}
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("The element is not present"
" in array")
: printf("The element is present at "
"index %d",
result);
return 0;
}
đầu ra Phần tử có mặt tại chỉ số 3 Giả sử T(N) là độ phức tạp thời gian của tìm kiếm nhị phân cho một tập N phần tử. Sau đó, T(N) = T(N/2) + O(1) (Bằng quan hệ truy hồi) - (i) Bây giờ, áp dụng Định lý Masters để tính toán độ phức tạp thời gian chạy của quan hệ truy hồi i. e T(N) = aT(N/b) + f(N) - (ii) So sánh phương trình (ii) với (i), ta được, a = 1, b = 2 Do đó, log (a cơ số b) = 1 = c - (iii) Bây giờ, f(N) = n^c log^k(n) //k = 0 - (iv) Sử dụng (iii) và (iv) trong phương trình (ii), chúng tôi nhận được, T(N) = O(N^c log^(k+1)N) = O(log(N)) - (v) Đây là độ phức tạp thời gian trong trường hợp xấu nhất cho tìm kiếm nhị phân. Bây giờ, trường hợp tốt nhất trong đó so sánh duy nhất được thực hiện. Do đó, N = 1. Vì vậy, chúng tôi nhận được, O(log(1)) = O(1) (như log(1) = 1) Do đó, độ phức tạp về thời gian cho Tìm kiếm nhị phân trong các trường hợp khác nhau là Trường hợp tốt nhất Ô(1) Trường hợp xấu nhất O(log n) Ưu và nhược điểm của tìm kiếm nhị phân trong CThuận lợi
Nhược điểm
Hoàn thành chương trình Không có cách duy nhất có thẩm quyền để triển khai Tìm kiếm nhị phân trong C. Do đó, khả năng là vô tận. Một vài ví dụ được đề cập trong bài viết chỉ là một số trong rất nhiều Hiểu biết về cách hoạt động của tìm kiếm nhị phân không chỉ quan trọng để đạt được sự thỏa đáng trong C mà còn trong các ngôn ngữ lập trình khác Bạn có biết bất kỳ cách thú vị/hiệu quả nào khác để viết Tìm kiếm nhị phân trong chương trình C không? Tìm kiếm nhị phân trong C là gì?Tìm kiếm nhị phân trong C
. Kỹ thuật tìm kiếm nhị phân chỉ hoạt động trên một mảng được sắp xếp, vì vậy một mảng phải được sắp xếp để áp dụng tìm kiếm nhị phân trên mảng. a sorting algorithm, that is used to search an element in a sorted array. A binary search technique works only on a sorted array, so an array must be sorted to apply binary search on the array.
C có tích hợp tìm kiếm nhị phân không?Tìm kiếm nhị phân trong chương trình C
. Nếu các yêu cầu yêu cầu sử dụng tìm kiếm nhị phân trên một mảng chưa được sắp xếp, thì nó cần được sắp xếp trước khi sử dụng thuật toán tìm kiếm nhị phân trên đó. Although it can only be used for sorted arrays, it is fast in comparison to the linear search. If the requirements ask for using binary search on an unsorted array, then it needs to be sorted first before using the binary search algorithm on it.
Độ phức tạp thời gian của tìm kiếm nhị phân trong C là gì?Độ phức tạp về thời gian của thuật toán tìm kiếm nhị phân là O(log n) . Độ phức tạp thời gian trong trường hợp tốt nhất sẽ là O(1) khi chỉ số trung tâm khớp trực tiếp với giá trị mong muốn. Tìm kiếm nhị phân trường hợp xấu nhất khác với trường hợp đó.
Tìm kiếm nhị phân với một ví dụ là gì?Tìm kiếm nhị phân ví dụ
. You have an array of 10 digits, and the element 59 needs to be found. Tất cả các phần tử được đánh dấu bằng chỉ số từ 0 – 9. Bây giờ, phần giữa của mảng được tính. Để làm như vậy, bạn lấy các giá trị ngoài cùng bên trái và bên phải của chỉ mục và chia chúng cho 2. |
