Tìm kiếm nhị phân

Ý tưởng của thuật toán: 
Phép tìm kiếm nhị phân được thực hiện trên dãy khoá có thứ tự (xét dãy tăng dần):
 a[0]<=a[1]<=a[2]<=...<=a[n-1]. Giá trị cần tìm x.



Chia đôi dãy khoá cần tìm kiếm. So sánh khoá giữa dãy với x, có 3 trường hợp xãy ra:
-  Giá trị khoá này bằng x, tìm kiếm thành công
-  Giá trị khoá này lớn hơn x, thì ta tiến hành tìm x với nữa bên trái của khoá này
-  Giá trị khoá này nhỏ hơn x, thì ta tiến hành tìm x với nữa bên phải của khoá này

Trường hợp tìm kiếm thất bại khi dãy khoá cần tìm không có phần tử nào.

Cài đặt Thuật toán [code Turbo C\C++]:

/*Thuật toán tìm kiếm nhị phân không đệ quy*/

int BinarySearch(int x, int a[],int n) // Tìm khoá x trong dãy a1,a2…,an
{

 int  left =0; //Left trỏ về chỉ số đầu dãy
 int right =n-1; //right trỏ về vị trí cuối dãy
 int mid; // mid trỏ vào giữa dãy
 int found = 0; //dùng để xác tìm thành công hay không (0: không tìm thấy, 1: tìm thấy)

 while (left <= right && found==0){
    mid = (left + right) / 2;//mid ở giữa dãy
    if (a[mid]== x) //trường hợp tìm thấy dừng thuật toán
       found = 1;
     else
          if (a[mid]<x)
              left = mid +1; //xác định lại đoạn tìm tiếp theo là bên phải
          else
              right = mid -1; //xác định lại đoạn tìm tiếp theo là bên trái
  }

return found;
}

/*Thuật toán tìm kiếm nhị phân đệ quy*/

int BinSearch(int[] a, int gt, int dau, int cuoi)
{
    int i, j;
    i = dau; j = cuoi;
    if (i > j)
   {
        return -1; // không tìm thấy
    }
    int giua = (i + j) / 2;
    if (gt == a[giua])
      {
          return giua; // tìm thấy
       }
    else if (gt < a[giua])
      {
          j = giua - 1;
          return BinSearch(a, gt, dau, j);
       }
    else
      {
          i = giua + 1;
          return BinSearch(a, gt, i, cuoi);
       }
   }