thuật toán tìm kiếm nhị phân

/*thuật toán tìm kiếm nhị phân
Được áp dụng trên mảng đã có thứ tự.
Ý tưởng: .
Giả xử ta xét mảng có thứ tự tăng, khi ấy ta có
ai-1<ai<ai+1
Nếu X>ai thì X chỉ có thể xuất hiện trong đoạn [ai+1, an-1]
Nếu X<ai thì X chỉ có thể xuất hiện trong đoạn [a0,   ai-1]
Ý tưởng của giải thuật là tại mỗi bước ta so sánh X với phần tử đứ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.
Giả sử dãy tìm kiếm hiện hành bao gồm các phần tử nằm trong aleft, aright, các bước của giải thuật như sau:
Bước 1: left=0; right=N-1;
Bước 2:
mid=(left+right)/2; //chỉ số phần tử giữa dãy hiện hà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 :  Right= mid-1;
a[mid]<x : Left= mid+1;
Bước 3: Nếu Left <=Right ; //  còn phần tử trong dãy hiện  hành
+ Lặp lại bước 2
Ngược lại : Dừng
Hàm trả về giá trị 1 nếu tìm thấy, ngược lại hàm trả về giá trị 0

*/
#include<iostream>
using namespace std;
int tim(int a[], int left,int right, int x)
{
do
{
if (x == a[(left + right) / 2]) return 1;
if (a[(left + right) / 2] > x) right = (left + right) / 2 - 1;
else left = (left + right) / 2 + 1;
} while (left <= right);
}
void main()
{
int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
cout << tim(a, 0, 9, 1);
}

Không có nhận xét nào:

Đăng nhận xét