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.
Đáp án : 1. Phần tử có giá trị nhỏ nhất trong dãy được tìm thấy và đổi chỗ cho phần tử đứng đầu dãy.
#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!
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.
Vì tìm kiếm nhị phân cần danh sách đã sắp xếp để biết chắc phần tử cần tìm nằm ở bên trái hay bên phải. Nếu không sắp xếp, ta không thể loại bỏ nửa danh sách một cách chính xác
Cách làm theo tìm kiếm nhị phân:
- Xác định khoảng cần tìm: từ 1001 đến 1500.
- Tìm số ở giữa: \(\frac{1001 + 1500}{2} = 1250 , 5 \approx 1250\).
- So sánh 1320 với 1250. Vì 1320 > 1250, ta bỏ nửa trái (1001 → 1250), chỉ giữ nửa phải (1251 → 1500).
- Lấy số giữa của khoảng mới: \(\frac{1251 + 1500}{2} = 1375 , 5 \approx 1375\).
- So sánh 1320 với 1375. Vì 1320 < 1375, ta bỏ nửa phải (1375 → 1500), chỉ giữ nửa trái (1251 → 1374).
- Lấy số giữa của khoảng mới: \(\frac{1251 + 1374}{2} = 1312 , 5 \approx 1312\).
- So sánh 1320 với 1312. Vì 1320 > 1312, ta bỏ nửa trái, giữ nửa phải (1313 → 1374).
- Lấy số giữa: \(\frac{1313 + 1374}{2} = 1343 , 5 \approx 1343\).
- So sánh 1320 với 1343. Vì 1320 < 1343, ta giữ nửa trái (1313 → 1342).
- Lấy số giữa: \(\frac{1313 + 1342}{2} = 1327 , 5 \approx 1327\).
- So sánh 1320 với 1327. Vì 1320 < 1327, ta giữ nửa trái (1313 → 1326).
- Lấy số giữa: \(\frac{1313 + 1326}{2} = 1319 , 5 \approx 1319\).
- So sánh 1320 với 1319. Vì 1320 > 1319, ta giữ nửa phải (1320 → 1326).
- Lấy số giữa: \(\frac{1320 + 1326}{2} = 1323\).
- So sánh 1320 với 1323. Vì 1320 < 1323, ta giữ nửa trái (1320 → 1322).
- Lấy số giữa: \(\frac{1320 + 1322}{2} = 1321\).
- So sánh 1320 với 1321. Vì 1320 < 1321, ta giữ nửa trái (1320 → 1320).
- Còn lại đúng một số 1320 → tìm thấy chiếc điện thoại cần mua. ✅
Chọn \(A\).