Thuật toán tìm kiếm nhị phân là một thuật toán dựa trên cơ chế so sánh và phân tách. Thuật toán tìm kiếm nhị phân còn được gọi là tìm kiếm nửa khoảng, tìm kiếm theo lôgarit hoặc tìm kiếm nhị phân . Thuật toán tìm kiếm nhị phân, tìm kiếm vị trí của giá trị đích trong một mảng được sắp xếp. Nó so sánh giá trị đích với phần tử giữa của mảng. Nếu phần tử bằng với phần tử đích thì thuật toán trả về chỉ mục của phần tử tìm được. Và nếu chúng không bằng nhau, thuật toán tìm kiếm sẽ sử dụng một nửa phần của mảng đó, Dựa trên việc so sánh giá trị, thuật toán sử dụng một trong hai phần đầu (khi giá trị nhỏ hơn phần giữa) và nửa sau ( khi giá trị lớn hơn giữa). Và làm tương tự cho nửa mảng tiếp theo.
Input:
A[] = {0,2,6,11,12,18,34,45,55,99}
n=55
Output:
55 at Index = 8 Giải thích
Đối với mảng của chúng tôi -
Chúng tôi sẽ so sánh 55, với phần tử giữa của mảng là 18, nhỏ hơn 55, vì vậy chúng tôi sẽ sử dụng nửa sau của mảng, tức là mảng {24, 45, 55, 99}, một lần nữa ở giữa là 55. Kiểm tra giá trị của phần tử tìm kiếm với nó. Và giá trị được khớp, sau đó chúng tôi sẽ trả về chỉ mục của giá trị này với là 8.
Nếu phần tử tìm kiếm sẽ nhỏ hơn phần giữa so với phần giữa chúng tôi đã sử dụng phần đầu và tiếp tục cho đến khi phần tử được tìm thấy ở phần giữa của mảng.
Để thực hiện tìm kiếm nhị phân, chúng ta có thể viết mã theo hai cách. hai cách này chỉ trì hoãn theo cách chúng ta gọi là hàm kiểm tra phần tử tìm kiếm nhị phân. họ là:
-
Sử dụng lặp lại - điều này có nghĩa là sử dụng một vòng lặp bên trong hàm để kiểm tra sự bình đẳng của phần tử giữa.
-
Sử dụng Trong phương thức này, hàm tự gọi lại nhiều lần với một bộ giá trị khác.
Ví dụ
#include<stdio.h>
int iterativeBsearch(int A[], int size, int element);
int main() {
int A[] = {0,12,6,12,12,18,34,45,55,99};
int n=55;
printf("%d is found at Index %d \n",n,iterativeBsearch(A,10,n));
return 0;
}
int iterativeBsearch(int A[], int size, int element) {
int start = 0;
int end = size-1;
while(start<=end) {
int mid = (start+end)/2;
if( A[mid] == element) {
return mid;
} else if( element < A[mid] ) {
end = mid-1;
} else {
start = mid+1;
}
}
return -1;
} Đầu ra
55 is found at Index 8
Ví dụ
#include<stdio.h>
int RecursiveBsearch(int A[], int start, int end, int element) {
if(start>end) return -1;
int mid = (start+end)/2;
if( A[mid] == element ) return mid;
else if( element < A[mid] )
RecursiveBsearch(A, start, mid-1, element);
else
RecursiveBsearch(A, mid+1, end, element);
}
int main() {
int A[] = {0,2,6,11,12,18,34,45,55,99};
int n=55;
printf("%d is found at Index %d \n",n,RecursiveBsearch(A,0,9,n));
return 0;
} Đầu ra
55 is found at Index 8