 |
| Tìm kiếm nhị phân |
Chào các bạn mình xin được giới thiệu đến các bạn thuật toán rất hữu ích trong việc tìm kiếm phần tử trong mảng. Đó chính là thuật toán Tìm kiếm nhị phân.
» Điều kiện áp dụng của thuật toán tìm kiếm nhị phân là mảng phải được sắp xếp.
» Ý tưởng:
- Giả sử ta xét mảng có thứ tự tăng dần. Khi đó A[i – 1] < A[i] < A[i + 1]
- Nếu mà số X cần tìm kiếm lớn hơn A[i] thì chắc chắn nó sẽ nằm trong đoạn A[i + 1] cho đến A[n – 1]
- Nếu mà số X cần tìm kiếm nhỏ hơn A[i] thì chắc chắn nó sẽ nằm trong đoạn A[0] cho đến A[i- 1]
- Ý tưởng của giải thuật là tại mỗi bước so sách X với phần đứng giữa trong dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này mà ta quyết định giới hạn dãy tìm kiếm ở nửa dưới hay ở nửa trên của dãy tìm kiếm hiện hành
Dưới đây là giả mã của thuật toán tìm kiếm nhị phân :
Giả sử trong dãy tìm kiếm hiện hành bao gồm các phần tử nằm trong A[left] à A[right], các bước của giải thuật được thực hiện như sau:
» Bước 1: left = 0; right = 0
» Bước 2:
- mid = (left + right) / 2 //chỉ số phần tử giữu dãy hiện hành
- So sánh a[mid] với x:
- A[mid] = x //tìm thấy và dừng lại
- A[mid] > x: right = mid – 1
- A[mid] < x: left = mid + 1
» Bước 3:
Nếu left <= right;
Lặp lại bước 2;
Ngược lại dừng.
Cuối cùng là code demo cho chương trình tìm kiếm nhị phân :
#include <iostream>
#include <conio.h>
using namespace std;
#include <conio.h>
using namespace std;
//Nhap mang A
void Nhap(int *A, int nA)
{
for(int i = 0; i < nA; i++)
{
cout <<“\nNhap a[ “<<i <<” ]: “;
cin >> A[i];
}
}
void Nhap(int *A, int nA)
{
for(int i = 0; i < nA; i++)
{
cout <<“\nNhap a[ “<<i <<” ]: “;
cin >> A[i];
}
}
//Xuat mang A
void Xuat(int *A, int nA)
{
for(int i = 0; i < nA; i++)
{
cout <<A[i] << “\t”;
}
}
void Xuat(int *A, int nA)
{
for(int i = 0; i < nA; i++)
{
cout <<A[i] << “\t”;
}
}
//Sap xep mang A
void Sort(int *A, int nA)
{
for(int i = 0; i <= nA – 1; i++)
for(int j = i + 1; j < nA; j++)
if(A[i] > A[j])
swap(A[i], A[j]);
}
//Tim kiem co x trong mang hay k
int TimKiemNhiPhan(int*A, int nA, int x)
{
int left = 0;
int right = nA – 1;
int mid;
do
{
mid = (left + right) / 2;
if(A[mid] == x)
return 1;
else
if(A[mid] < x)
left = mid + 1;
else
right = mid – 1;
}while(left <= right);
return 0;
}
int main()
{
int nA;
cout <<“Nhap nA:”;
cin >> nA;
int* A = new int[nA];
Nhap(A, nA);
Xuat(A, nA);
int x;
cout <<“\nTim so may: “;
cin >>x;
Sort(A, nA);
if(TimKiemNhiPhan(A, nA, x) == 1)
cout <<“\nYes!”;
else
cout <<“\nNo!”;
delete[] A;
getch();
return 0;
}
void Sort(int *A, int nA)
{
for(int i = 0; i <= nA – 1; i++)
for(int j = i + 1; j < nA; j++)
if(A[i] > A[j])
swap(A[i], A[j]);
}
//Tim kiem co x trong mang hay k
int TimKiemNhiPhan(int*A, int nA, int x)
{
int left = 0;
int right = nA – 1;
int mid;
do
{
mid = (left + right) / 2;
if(A[mid] == x)
return 1;
else
if(A[mid] < x)
left = mid + 1;
else
right = mid – 1;
}while(left <= right);
return 0;
}
int main()
{
int nA;
cout <<“Nhap nA:”;
cin >> nA;
int* A = new int[nA];
Nhap(A, nA);
Xuat(A, nA);
int x;
cout <<“\nTim so may: “;
cin >>x;
Sort(A, nA);
if(TimKiemNhiPhan(A, nA, x) == 1)
cout <<“\nYes!”;
else
cout <<“\nNo!”;
delete[] A;
getch();
return 0;
}
Không có nhận xét nào:
Đăng nhận xét