Thuật toán tìm kiếm nhị phân thực hiện tìm kiếm một mảng đã sắp xếp bằng cách liên tục chia các khoảng tìm kiếm thành 1 nửa. Bắt đầu với một khoảng từ phần tử đầu mảng, tới cuối mảng. Nếu giá trị của phần tử cần tìm nhỏ hơn giá trị của phần từ nằm ở giữa khoảng thì thu hẹp phạm vi tìm kiếm từ đầu mảng tới giửa mảng và nguợc lại. Cứ thế tiếp tục chia phạm vi thành các nửa cho dến khi tìm thấy hoặc đã duyệt hết.

Thuật toán tìm kiếm nhị phân tỏ ra tối ưu hơn so với tìm kiếm tuyết tính ở các mảng có độ dài lớn và đã được sắp xếp. Ngược lại, tìm kiếm tuyến tính sẽ tỏ ra hiệu quả hơn khi triển khai trên các mảng nhỏ và chưa được sắp xếp.

#include <bits/stdc++.h>

using namespace std;

long long x,i,n,k;

int main()

{

cin>>n>>k;

for (i=1; i<=n; i++)

{

cout<<x;

if (x==k) cout<<i<<" ";

}

return 0;

}

Code:

Kết quả:

k = 4

i = 1
Số 2 : Không đúng số cần tìm
i = 2
Số 3 : Không đúng số cần tìm
i = 3
Số 4 : Đúng số cần tìm nhưng chưa hết dãy số

Chọn C

a. Ví dụ một bài toán tìm kiếm trong thực tế: Giáo viên muốn tìm tên bạn Chung trong danh sách lớp sau:

Các bước thực hiện thuật toán tìm kiếm nhị phân cho bài toán trên:

- Bước 1: Xét vị trí ở giữa dãy, đó là vị trí số 5

- Vì sau bước 2 đã tìm thấy tên học sinh nên thuật toán kết thúc.

b) Thuật toán tìm kiếm nhị phân

- Thuật toán tìm kiếm nhị phân thu hẹp được phạm vi tìm kiếm chỉ còn tối đa là một nửa sau mỗi lần lặp. Thuật toán chia bài toán thành những bài toán nhỏ hơn giúp tăng hiệu quả tìm kiếm.

Thuật toán tuần tự

- Mô tả thuật toán phải cụ thể, rõ ràng, đầy đủ, đầu vào là gì, đầu ra là gì và chỉ rõ sự kết thúc thuật toán.

- Cần mô tả thuật toán cho tốt thì người máy hay máy tính mới hiểu đúng và thực hiện được.

- Nếu không, kết quả thực hiện thuật toán có thể không như mong đợi.

i=3

#include <bits/stdc++.h>

using namespace std;

long long x,i,n,k;

int main()

{

cin>>n>>k;

for (i=1; i<=n; i++)

{

cout<<x;

if (x==k) cout<<i<<" ";

}

return 0;

}

#include <bits/stdc++.h>

using namespace std;

long long x,i,n,k;

int main()

{

cin>>n>>k;

for (i=1; i<=n; i++)

{

cout<<x;

if (x==k) cout<<i<<" ";

}

return 0;

}

#include <bits/stdc++.h>

using namespace std;

long long x,i,n,k;

int main()

{

cin>>n>>k;

for (i=1; i<=n; i++)

{

cout<<x;

if (x==k) cout<<i<<" ";

}

return 0;

}