Tìm kiếm nhị phân

Cấu trúc dữ liệu và giải thuật - Đệ quy

Đề bài : Viết chương trình c tìm kiếm phần tử trong mảng 1 chiều bằng tìm kiếm nhị phân

*Lưu ý:

Tìm kiếm nhị phân (Binary Search) áp dụng cho các dãy phần tử đã được sắp xếp tăng dần hoặc giảm dần. Binary Search sử dụng nguyên lý nổi tiếng của “lý thuyết thông tin”(Information Theroy).

Ý tưởng:

Vì dãy đã có trật tự (ví dụ thứ tự tăng) nên các phần tử trong dãy có quan hệ tuyến tính a₁<a₂<a₃<…<a_n<a_n+1. Giả sử phải xác định xem khóa x (phần tử tìm kiếm) có trong dãy không. Cần giải quyết 2 tình huống:

• X<a(i) thi chắc chắn x chỉ tồn tại trong đoan a[1,i]
• X>a(i) thì chắc chắn x chỉ tồn tại trong đoạn a[i,n]

Trong 2 tình huống người ta gọi a(i) là mốc để so sánh

Các bước của thuật toán:

1. Gián left=1; right=n;(left là phần tử đầu, right là phần tử cuối)
2. Trong khi chưa xét hết các phần tử của dãy (tức là d<=c) thì làm các việc sau
3. Tính điểm giữa: mid=(left+ right)/2
4. So sánh khóa(phần tử cần tìm) với mid

• Nếu x<a[mid] thì left = mid-1
• Nếu x>a[mid] thì right = mid+1
• Nếu a[mid] = x -> thông báo tìm thấy -> kết thúc
• Nếu a[mid] khác x -> quay lại bước a -> thông báo không tìm thấy

Cài đặt:

#include<iostream> #include<stdlib.h> #include<stdio.h> #include<conio.h> #include<string.h> #include<math.h> #include<ctype.h> #include<assert.h> using namespace std; void nhap (int a[],int &n) { cout<<"\n Nhap so phan tu cua mang: "; cin>>n; for(int i=0;i<n;i++) cin>>a[i]; } void xuat(int a[],int n) { cout<<"\n Cac phan tu trong mang: "; for(int i=0;i<n;i++) cout<<a[i]<<" "; } void sapxep(int a[],int n) { for(int i=0;i<n-1;i++) for(int j=i+1;j<n;j++) if(a[i]>a[j]) swap(a[i],a[j]); } int timkiemnhiphan(int a[],int n,int x) { int trai=0,phai=n-1,giua;int ketqua=-1; while(trai<=phai) { giua=(trai+phai)/2; if(a[giua]>x) phai=giua-1; else if(a[giua]<x) trai=giua+1; else { ketqua=giua; break; } } return ketqua; } int main() { int a[1000],n,x,k; nhap(a,n); xuat(a,n); sapxep(a,n); cout<<"\nnhap so can tim:"; cin>>x; k=timkiemnhiphan(a,n,x); if(k==-1) cout<<"\nkhong co trong mang! "<<endl; else cout<<"\n so "<<x<<" nam o vi tri thu "<<k<<" trong mang"<<endl; }

Kết quả khi chạy chương trình:

Độ phức tạp của thuật toán :

• Tốt nhất: O(1)
• Xấu nhất: O(log₂n)
• Ngẫu nhiên: O(log₂(n/2))

Được viết bởi Đinh Quang Trưởng

cấu trúc dữ liệu và giải thuật Đệ Quy 3:05 PM