Ý tưởng
*Áp dụng đối với những dãy số đã có thứ tự(đã được sắp xếp tăng dần hoặc giảm dần).
*Giải thuật tìm cách giới hạn phạm vi tìm kiếm sau mỗi lần so sánh x với một phần tử trong dãy. Ý tưởng của giải thuật là tại mỗi bước tiến hành so sánh x với phần tử nằm ở vị trí giữa của dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này để quyết định giới hạn dãy tìm kiếm ở bước kế tiếp là nửa trên hay nửa dưới của dãy tìm kiếm hiện hành.
Giải thuật
Bước 1: left = 1; right = N; // tìm kiếm trên tất cả các phần tử
Bước 2:
mid = (left+right)/2; // lấy mốc so sánh
So sánh a[mid] với x, có 3 khả năng :
¢a[mid] = x: Tìm thấy. Dừng
¢a[mid] > x: //tìm tiếp x trong dãy con aleft .. amid -1
right =mid - 1;
¢a[mid] < x: //tìm tiếp x trong dãy con amid +1 .. aright
left = mid + 1;
Bước 3:
Nếu left <= right //còn phần tử chưa xét tìm tiếp.
Lặp lại Bước 2.
Ngược lại: Dừng //Ðã xét hết tất cả các phần tử.
Cài đặt
int BinarySearch(int a[],int N,int x )
{ int left =0; right = N-1;
int mid;
do{
mid = (left + right)/2;
if (x == a[mid])
{ int left =0; right = N-1;
int mid;
do{
mid = (left + right)/2;
if (x == a[mid])
return mid;//Thấy x tại mid
else if (x < a[mid])
right = mid -1;
else
else
left = mid +1;
}while (left <= right);
return -1; // Tìm hết dãy mà không có x
}while (left <= right);
return -1; // Tìm hết dãy mà không có x
}
Kết quả trả về là vị trí của x trong mảng. Nếu trả về -1 là không có x trong mảng
Kết quả trả về là vị trí của x trong mảng. Nếu trả về -1 là không có x trong mảng