MảngTìm kiếm nhị phân
Mô tả
Tại rạp CGV Vincom Đồng Khởi, bảng giá vé luôn được quản lý theo thứ tự tăng dần để nhân viên dễ tra cứu. Hôm nay rạp mở thêm một hạng ghế mới với đơn giá riêng, bạn cần chèn giá này vào đúng vị trí trong mảng đã sắp để trật tự không bị phá vỡ.
Cho mảng gia gồm n phần tử đã sắp xếp tăng dần (không giảm) và một giá giaMoi. Hãy tìm chỉ số mà giaMoi cần được chèn vào, sao cho sau khi chèn mảng vẫn tăng dần. Nếu đã có phần tử bằng giaMoi, hãy chèn vào ngay bên phải của phần tử đó (chỉ số lớn hơn tất cả phần tử bằng giaMoi).
Đầu vào
gia: mảng số nguyên đã sắp xếp tăng dần.giaMoi: số nguyên là đơn giá cần chèn.
Đầu ra
- Trả về một số nguyên là chỉ số vị trí chèn
giaMoi.
Ràng buộc
0 <= n <= 10^5- Mỗi phần tử trong
giavàgiaMoicó giá trị0 <= x <= 10^6. - Mảng
giađảm bảo đã sắp xếp không giảm.
Ví dụ
Ví dụ 1
- Đầu vào:
gia = [25000, 35000, 45000, 60000],giaMoi = 40000 - Đầu ra:
2 - Giải thích:
40000lớn hơn35000(chỉ số 1) và nhỏ hơn45000(chỉ số 2), nên chèn tại chỉ số 2. Mảng kết quả:[25000, 35000, 40000, 45000, 60000].
Ví dụ 2
- Đầu vào:
gia = [25000, 35000, 35000, 60000],giaMoi = 35000 - Đầu ra:
3 - Giải thích: Đã có
35000tại các chỉ số 1 và 2. Theo quy tắc chèn bên phải mọi phần tử bằng, vị trí là3. Mảng kết quả:[25000, 35000, 35000, 35000, 60000].