Hãy nhập câu hỏi của bạn vào đây, nếu là tài khoản VIP, bạn sẽ được ưu tiên trả lời.
Sự khác biệt cơ bản nhất là thuật toán tìm kiếm nhị phân yêu cầu dữ liệu phải được sắp xếp, trong khi thuật toán tìm kiếm tuần tự không có yêu cầu này. Ngoài ra, cách thức tìm kiếm của thuật toán nhị phân là chia để trị, còn thuật toán tuần tự là duyệt lần lượt từng phần tử
Tìm kiếm tuần tự duyệt từng phần tử một, không cần sắp xếp. Tìm kiếm nhị phân chia đôi danh sách mỗi bước, cần sắp xếp trước.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll a[]={10,2,5,12,20,6,8,15,18}; //mảng đã cho
ll n=sizeof(a)/sizeof(a[0]); //độ dài mảng
sort(a,a+n); //sắp xếp mảng
//Thuật toán tìm kiếm nhị phân
ll l=0, r=n-1;
while(l<=r) {
ll mid=(l+r)/2; //Tìm phần tử giữa left và right
if(a[mid]<15) l=mid+1; //Vì từ đoạn [0,mid] thì phần tử nhỏ hơn 15 nên ta duyệt từ khoảng (mid,r]
else r=mid-1; //vì thấy nên rút r để thu hẹp phạm vi
}
cout << l+1; //in ra kq (vì bắt đầu từ 0 đến n-1 nên phải tăng thêm để ra vị trí đúng)
}
(Bạn có thể dựa vào code mình để rút ra các bước)
Chúc bạn học tốt!
Câu 1. Ví dụ bài toán tìm kiếm trong thực tế: Tìm kiếm một tên khách hàng trong danh sách các khách hàng của cửa hàng.
Câu 2. Ý tưởng sử dụng thuật toán tìm kiếm tuần tự:
Bạn có danh sách các tên khách hàng trong cửa hàng.
Thuật toán tìm kiếm tuần tự sẽ kiểm tra từng tên khách hàng trong danh sách, bắt đầu từ đầu.
Mỗi lần kiểm tra, thuật toán so sánh tên cần tìm với tên ở vị trí hiện tại trong danh sách.
Nếu tìm thấy tên khách hàng cần tìm, thuật toán dừng lại và trả về kết quả.
Nếu không tìm thấy sau khi kiểm tra hết tất cả các tên, thuật toán sẽ thông báo không tìm thấy.