Cho mảng gồm n số nguyên đã được sắp xếp theo thứ tự không giảm và một số nguyên x.
Yêu cầu: Tìm vị trí của x trong mảng bằng thuật toán tìm kiếm nhị phân. Nếu x không tồn tại thì in -1.
Dữ liệu vào: Dòng đầu chứa hai số nguyên n và x (1 ≤ n ≤ 105). Dòng thứ hai chứa n số nguyên đã được sắp xếp theo thứ tự không giảm.
Dữ liệu ra: In vị trí của x (đánh số từ 1). Nếu không tìm thấy thì in -1.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 7 8 1 3 5 8 9 12 15 |
4 | Số 8 nằm ở vị trí thứ 4 của mảng. |
Giới hạn:
Yêu cầu: Chương trình phải sử dụng tìm kiếm nhị phân.
Cho mảng gồm n số nguyên đã được sắp xếp theo thứ tự không giảm và một số nguyên x.
Yêu cầu: Kiểm tra xem x có xuất hiện trong mảng hay không bằng thuật toán tìm kiếm nhị phân.
Dữ liệu vào: Dòng đầu chứa hai số nguyên n và x (1 ≤ n ≤ 105). Dòng thứ hai chứa n số nguyên đã được sắp xếp.
Dữ liệu ra: In YES nếu x tồn tại, ngược lại in NO.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra |
|---|---|
| 6 10 2 4 6 8 10 12 |
YES |
Giới hạn:
Yêu cầu: Chương trình phải sử dụng tìm kiếm nhị phân.
Cho mảng gồm n số nguyên đã được sắp xếp theo thứ tự không giảm và một số nguyên x.
Yêu cầu: Đếm số lần xuất hiện của x trong mảng bằng thuật toán tìm kiếm nhị phân.
Dữ liệu vào: Dòng đầu chứa hai số nguyên n và x (1 ≤ n ≤ 105). Dòng thứ hai chứa n số nguyên đã được sắp xếp.
Dữ liệu ra: In số lần xuất hiện của x.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 8 5 1 3 5 5 5 8 9 10 |
3 | Số 5 xuất hiện 3 lần trong mảng. |
Giới hạn:
Yêu cầu: Chương trình phải sử dụng tìm kiếm nhị phân.
Cho mảng gồm n số nguyên đã được sắp xếp theo thứ tự không giảm và một số nguyên x.
Yêu cầu: Tìm vị trí xuất hiện đầu tiên của x trong mảng bằng thuật toán tìm kiếm nhị phân. Nếu không tồn tại thì in -1.
Dữ liệu vào: Dòng đầu chứa hai số nguyên n và x (1 ≤ n ≤ 105). Dòng thứ hai chứa n số nguyên đã được sắp xếp.
Dữ liệu ra: In vị trí đầu tiên của x (đánh số từ 1), hoặc -1 nếu không tồn tại.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra |
|---|---|
| 8 5 1 3 5 5 5 8 9 10 |
3 |
Yêu cầu: Chương trình phải sử dụng tìm kiếm nhị phân.
Cho mảng gồm n số nguyên đã được sắp xếp theo thứ tự không giảm và một số nguyên x.
Yêu cầu: Tìm vị trí xuất hiện cuối cùng của x trong mảng bằng thuật toán tìm kiếm nhị phân. Nếu không tồn tại thì in -1.
Dữ liệu vào: Dòng đầu chứa hai số nguyên n và x (1 ≤ n ≤ 105). Dòng thứ hai chứa n số nguyên đã được sắp xếp.
Dữ liệu ra: In vị trí cuối cùng của x (đánh số từ 1), hoặc -1 nếu không tồn tại.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra |
|---|---|
| 8 5 1 3 5 5 5 8 9 10 |
5 |
Yêu cầu: Chương trình phải sử dụng tìm kiếm nhị phân.
Cho mảng gồm n số nguyên đã được sắp xếp theo thứ tự không giảm và một số nguyên x.
Yêu cầu: Tìm vị trí của phần tử đầu tiên có giá trị không nhỏ hơn x. Nếu không tồn tại thì in -1.
Dữ liệu vào: Dòng đầu chứa hai số nguyên n và x (1 ≤ n ≤ 105). Dòng thứ hai chứa n số nguyên đã được sắp xếp.
Dữ liệu ra: In vị trí tìm được (đánh số từ 1), hoặc -1 nếu không tồn tại.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra |
|---|---|
| 7 6 1 3 5 7 9 11 13 |
4 |
Yêu cầu: Chương trình phải sử dụng tìm kiếm nhị phân.
Cho mảng gồm n số nguyên đã được sắp xếp theo thứ tự không giảm và một số nguyên x.
Yêu cầu: Tìm vị trí của phần tử đầu tiên có giá trị lớn hơn x. Nếu không tồn tại thì in -1.
Dữ liệu vào: Dòng đầu chứa hai số nguyên n và x (1 ≤ n ≤ 105). Dòng thứ hai chứa n số nguyên đã được sắp xếp.
Dữ liệu ra: In vị trí tìm được (đánh số từ 1), hoặc -1 nếu không tồn tại.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra |
|---|---|
| 7 7 1 3 5 7 7 9 12 |
6 |
Yêu cầu: Chương trình phải sử dụng tìm kiếm nhị phân.
Cho mảng gồm n số nguyên đã được sắp xếp theo thứ tự không giảm và một số nguyên x.
Yêu cầu: Tìm vị trí của phần tử cuối cùng có giá trị không lớn hơn x. Nếu không tồn tại thì in -1.
Dữ liệu vào: Dòng đầu chứa hai số nguyên n và x (1 ≤ n ≤ 105). Dòng thứ hai chứa n số nguyên đã được sắp xếp.
Dữ liệu ra: In vị trí tìm được (đánh số từ 1), hoặc -1 nếu không tồn tại.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra |
|---|---|
| 7 8 1 3 5 7 9 11 13 |
4 |
Yêu cầu: Chương trình phải sử dụng tìm kiếm nhị phân.
Cho mảng gồm n số nguyên đã được sắp xếp theo thứ tự không giảm và một số nguyên x.
Yêu cầu: Tìm vị trí của phần tử cuối cùng có giá trị nhỏ hơn x. Nếu không tồn tại thì in -1.
Dữ liệu vào: Dòng đầu chứa hai số nguyên n và x (1 ≤ n ≤ 105). Dòng thứ hai chứa n số nguyên đã được sắp xếp.
Dữ liệu ra: In vị trí tìm được (đánh số từ 1), hoặc -1 nếu không tồn tại.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra |
|---|---|
| 7 7 1 3 5 7 9 11 13 |
3 |
Yêu cầu: Chương trình phải sử dụng tìm kiếm nhị phân.
Cho mảng gồm n số nguyên đã được sắp xếp theo thứ tự không giảm và một số nguyên x.
Yêu cầu: Tìm phần tử có giá trị gần x nhất. Nếu có nhiều phần tử cùng khoảng cách đến x thì in phần tử nhỏ hơn.
Dữ liệu vào: Dòng đầu chứa hai số nguyên n và x (1 ≤ n ≤ 105). Dòng thứ hai chứa n số nguyên đã được sắp xếp.
Dữ liệu ra: In giá trị của phần tử tìm được.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 7 8 1 3 5 7 9 11 13 |
7 | Hai số 7 và 9 đều cách 8 một đơn vị nên chọn số nhỏ hơn là 7. |
Giới hạn:
Yêu cầu: Chương trình phải sử dụng tìm kiếm nhị phân.
Có n sợi dây với độ dài cho trước và một số nguyên dương k.
Yêu cầu: Cắt các sợi dây thành những đoạn có cùng độ dài (độ dài là số nguyên dương) để thu được ít nhất k đoạn. Tìm độ dài lớn nhất có thể.
Dữ liệu vào: Dòng đầu chứa hai số nguyên n và k (1 ≤ n ≤ 105). Dòng thứ hai chứa độ dài của n sợi dây.
Dữ liệu ra: In độ dài lớn nhất tìm được.
| Dữ liệu vào | Dữ liệu ra |
|---|---|
| 4 5 8 7 6 5 |
5 |
Yêu cầu: Sử dụng tìm kiếm nhị phân trên đáp án.
Có n quyển sách, quyển thứ i có ai trang. Cần chia theo đúng thứ tự cho k học sinh, mỗi học sinh nhận một đoạn sách liên tiếp.
Yêu cầu: Tìm số trang lớn nhất mà một học sinh phải đọc là nhỏ nhất.
Dữ liệu vào: Dòng đầu chứa hai số nguyên n và k (1 ≤ k ≤ n ≤ 105). Dòng thứ hai chứa số trang của từng quyển sách.
Dữ liệu ra: In giá trị nhỏ nhất tìm được.
Yêu cầu: Sử dụng tìm kiếm nhị phân trên đáp án.
Cho một tấm gỗ hình chữ nhật có chiều dài a và chiều rộng b. Người ta muốn cắt tấm gỗ thành các hình vuông có cùng kích thước cạnh (độ dài cạnh là số nguyên dương).
Yêu cầu: Tìm độ dài cạnh lớn nhất của hình vuông để có thể cắt được ít nhất k hình vuông.
Dữ liệu vào: Một dòng chứa ba số nguyên a, b và k (1 ≤ a, b ≤ 109, 1 ≤ k ≤ 109).
Dữ liệu ra: In độ dài cạnh lớn nhất tìm được.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| 12 8 6 | 4 | Cắt được 3 × 2 = 6 hình vuông cạnh 4. |
Giới hạn:
Gợi ý: Nếu chọn cạnh hình vuông là x thì số hình vuông cắt được là (a / x) × (b / x). Hãy sử dụng tìm kiếm nhị phân trên đáp án để tìm cạnh lớn nhất thỏa mãn.
Một nhà máy có n sản phẩm cần đóng gói theo đúng thứ tự. Khối lượng của sản phẩm thứ i là ai.
Yêu cầu: Đóng gói các sản phẩm vào không quá k thùng, mỗi thùng chứa một đoạn sản phẩm liên tiếp. Tìm khối lượng lớn nhất của một thùng là nhỏ nhất.
Dữ liệu vào: Dòng đầu chứa hai số nguyên n và k (1 ≤ k ≤ n ≤ 105). Dòng thứ hai chứa n số nguyên ai (1 ≤ ai ≤ 109).
Dữ liệu ra: In giá trị nhỏ nhất của khối lượng lớn nhất trong các thùng.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra |
|---|---|
| 5 3 2 3 4 5 6 |
9 |
Giới hạn:
Gợi ý: Giả sử khối lượng lớn nhất của mỗi thùng là x. Hãy kiểm tra có thể đóng gói tất cả sản phẩm vào không quá k thùng hay không. Sử dụng tìm kiếm nhị phân trên đáp án để tìm giá trị nhỏ nhất của x.