Solutions of Binary search

Select solution language

benjamin_tom Created at 0 likes

# Ý tưởng - Sử dụng chặt nhị phân để tìm x trong mảng đã sắp xếp ## Nếu tìm thấy x thì trả về mid + 1, vì theo đề mảng chạy từ 1 đến n ``` if(a[mid]==x) return mid+1; ``` ## Nếu a[mid] < x thì tìm ở nửa bên phải ``` else if(a[mid] < x) l = mid+1; ``` ## Nếu a[mid] > x thì tìm ở nửa trái ``` else r = mid-1; ``` ## CHÚ Ý: Để sử dụng tìm kiếm nhị phân thì mảng phải được sắp xếp tăng dần ``` sort(a, a+n); ``` ## Code tham khảo: ### Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này ``` #include<bits/stdc++.h> using namespace std; int tknp(int a[], int n, int x){ int l = 0, r=n-1; while(l <= r){ int mid = (l+r)/2; if(a[mid]==x) return mid+1; else if(a[mid] < x) l = mid+1; else r = mid-1; } return 0; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; int a[n]; for(int i =0; i <n; ++i) cin >> a[i]; sort(a, a+n); while(q--){ int x; cin >> x; cout << tknp(a, n, x) << endl; } } // marisaoj ```