Kênh Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
Saturday, January 24, 2015

/*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);
}

0 comments:

Post a Comment

Popular Posts