Phương pháp tìm kiếm nhị phân chỉ có thể được áp dụng cho danh sách đã sắp xếp. Danh sách đã cho được chia thành hai phần bằng nhau. Trong danh sách, khóa được so sánh với phần tử giữa.
Ba tình huống có thể xảy ra trong tìm kiếm nhị phân như sau -
-
Nếu phần tử ở giữa khớp với khóa, thì quá trình tìm kiếm sẽ kết thúc thành công tại đây
-
Nếu phần tử ở giữa lớn hơn khóa, thì quá trình tìm kiếm sẽ được tiến hành ở phân vùng bên trái
-
Nếu phần tử ở giữa thấp hơn khóa, thì quá trình tìm kiếm sẽ được tiến hành trong phân vùng bên phải.
Đầu vào (i / p)
danh sách các phần tử được sắp xếp, khóa.
Đầu ra (o / p)
- Thành công - Nếu tìm thấy chìa khóa.
- Không thành công - Nếu không.
Ví dụ
Sau đây là chương trình C cho phương pháp tìm kiếm nhị phân -
#include<stdio.h>
int main(){
int a[50], n, i, key, flag = 0, low, mid, high;
printf("enter the no: of elements:");
scanf ("%d",&n);
printf("enter the elements:");
for(i=0; i<n; i++)
scanf( "%d", &a[i]);
printf("enter a key element:");
scanf ("%d", &key);
low = 0;
high = n-1;
while (low<= high ){
mid = (low + high) /2;
if (a[mid] == key){
flag = 1;
break;
} else {
if (a[mid] > key)
high = mid-1;
else
low = mid+1;
}
}
if (flag == 1)
printf ("search is successful");
else
printf("search is unsuccessful");
return 0;
} Đầu ra
Khi chương trình trên được thực thi, nó tạo ra kết quả sau -
enter the no: of elements:5 enter the elements:23 45 57 89 90 enter a key element:45 search is successful