---
# System prepended metadata

title: Tìm kiếm nhị phân

---

# Tìm kiếm nhị phân

### 1. Lý thuyết
#### a. Mục đích
- Tìm kiếm một phần tử trong một mảng đã sắp xếp
#### b. Áp dụng
- tìm kiếm phần tử
- tìm kiếm giới hạn trên và dưới


### 2. Code
```python=

a = [1,2,3,4,5,6,7,8,9,10]
def binarySearch(x, a, l, r):
    while l<=r:
        m = (l+r)//2
        if a[m] > x:
            r = m - 1
        elif a[m] < x:
            l = m + 1
        else:
            return m
    return -1 

l = 0
r = len(a) - 1
vt = binarySearch(8, a, l, r)
```

##### Bài 1:
```python=
a = list(input())
def binarySearch(a, l, r):
    while l<=r:
        m = (l+r)//2
        if a[m - 1] == '0' and a[m] == '1':
            return m -1
        elif a[m] == '0':
            l = m + 1
        else:
            r = m - 1
    return -1 

l = 0
r = len(a) - 1
binarySearch(a, l, r)
```

##### Bài 5:
1. Hướng tiếp cận:
- Chọn n phần tử sao cho n lớn nhất và trung bình cộng các phần tử bé k -> các phần tử được chọn phải bé nhất -> sắp xếp lại mảng a
- Đề bài có q truy vấn -> bảng lưu giá trị trung bình cộng tính tới phần tử thứ i của mảng a
-> trong mảng B thì Bi = sum(a[:i])/(i+1)
- áp dụng tìm kiếm nhị phân để tìm giá trị trung bình lớn nhất bé hơn k 
2. 
```python=
a = sorted(list(map(int, input().split())))
```

```python=
b = []
x = 0
l = 1
for i in a:
    x += i    
    b.append(x/i)
```