Tìm kiếm nhị phân và ứng dụng

TÌM KIẾM NHỊ PHÂN

Bài toán 1. Cho dãy a[1], a[2], ..., a[n] không giảm. Hãy tìm vị trí trong dãy a có giá trị bằng x.
Thuật toán: binary_search(a.begin(), a.end(), x)



Bài toán 2. Cho dãy a[1], a[2], ..., a[n] không giảm. Hãy tìm vị trí nhỏ nhất trong dãy a có giá trị lớn hơn hay bằng x.
Thuật toán: lower_bound(a.begin(), a.end(), x)


Bài toán 3. Cho dãy a[1], a[2], ..., a[n] không giảm. Hãy tìm vị trí nhỏ nhất trong dãy a có giá trị lớn hơn x.
Thuật toán: upper_bound(a.begin(), a.end(), x)


Ứng dụng của lower_bound và upper_bound
1. Tìm đoạn phần tử giá trị bằng x
vector<int>::interator l, r;
int left, right;

l = lower_bound(a.begin(), a.end(), x);
r = upper_bound(a.begin(), a.end(), x);

left = l-x.begin();
right = r-x.begin()-1;

2. Đếm số lượng phần tử nhỏ hơn x
left = lower_bound(a.begin(), a.end(), x);
nums= left-a.begin()-1;

2. Đếm số lượng phần tử lớn hơn x
right = lower_bound(a.begin(), a.end(), x);
nums= a.end()-right;