[ Search ] Tìm kiếm nhị phân [Code C++]

Thuật toán tìm kiếm nhị phân - Binary sort [Xem clip hướng dẫn và demo]

Ý 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);
       }
   }

// Đề nghị độc giả chuyể hàm cài trên sang đệ quy và viết đầy đủ chương trình để mo phỏng thuật toán.

>>>clip hướng dẫn và demo

[Tải Code Chương trình tại đây (Lưu ý: Sau 5s, click Bỏ qua quảng cáo - Skin Ad)]

---------------------------------------------
Xem thêm các thuật toán khác: 
1. Thuật toán tìm kiếm tuần tự
2. Thuật toán tìm kiếm nhị phân
3. Thuật toán sắp xếp đổi trực tiếp - Select sort
4. Thuật toán sắp xếp nổi bọt - Bubble sort
5. Thuật toán sắp xếp chèn trực tiếp - Insert sort
6. Thuật toán sắp xếp nhanh - Quick sort
7. Thuật toán sắp xếp hòa trộn - Merge sort
8. Thuật toán sắp xếp vun đống - Heap sort
9. Thuật toán sắp xếp shell - shell sort

0 nhận xét:

Cảm ơn bạn đã quan tâm tới bài viết này!