# 1. Tóm tắt đề bài

Cho một vector $nums$ được sắp xếp sẵn theo chiều tăng dần và một giá trị $target$. Tìm vị trí đầu tiên và cuối cùng của $target$ trong $nums$ hoặc trả về ${-1,-1}$ nếu đó là không thể.

### Giới hạn
$1 \le nums.size() \le 10^5$
$-10^9 \le nums[i],target \le 10^9$

# 2. Tóm tắt lời giải

**Độ phức tạp dự tính: $O(logN)$**

Tìm kiếm nhị phân

# 3. Lời giải chi tiết

Để giải quyết bài này trong $O(N)$ thì ta có thể duyệt tuần tự qua từng phần tử một để tìm kiếm. Tuy nhiên đề bài yêu cầu giải trong $O(logN)$ nên ta sẽ sử dụng phương pháp tìm kiếm nhị phân.

Nhận thấy vector đã được sort sẵn, vì vậy nếu ta chọn $1$ vị trí bất kì thì các số đứng trước nó sẽ luôn nhỏ hơn hoặc bằng nó và các số đằng sau sẽ luôn lớn hơn hoặc bằng nó.

Vì vậy, nếu ta xét một vị trí mà số đó lớn hơn hẳn $target$ thì ta sẽ không cần xét các vị trí sau đó nữa và tương tự nếu vị trí đó nhỏ hơn hẳn $target$ thì ta không cần xét các vị trí trước đó nữa.

Để làm được vậy, ta sẽ sử dụng 3 biến sau
* $left = 0$
* $right = nums.size()-1$
* $mid = (left+right+1)/2$

Nếu tại $mid$ ta thấy giá trị ở $mid \lt target$ thì không cần xét các giá trị trước đó nữa, vì vậy update $left = mid + 1$. Tương tự với trường hợp ngược lại, nếu $mid \gt target$ update $right = mid - 1$.

Và với trường hợp $mid = target$, ta cần kiểm tra xem mình đang tìm số đầu tiên hay cuối cùng của $target$. Khi tìm thấy một vị trí có giá trị bằng $target$, ta lưu nó trong biến $index$. Nếu ta đang tìm vị trí đầu tiên, update $right = mid - 1$, và $left = mid + 1$ nếu đi tìm vị trí cuối cùng.

Ta cứ làm vậy cho đến khi nào $left \gt right$. Nếu biến $index$ không nhận giá trị nào thì trong vector không có giá trị nào bằng $target$. Lúc này, ta trả về kết quả $-1,-1$.

### Độ phức tạp thuật toán

Thời gian: $O(logN)$

Độ phức tạp của thuật toán trên là logN bởi với mỗi lần ta xét một giá trị $mid$, ta có thể loại trừ được $1/2$ độ dài của phần còn lại chưa được xét. Vì vậy, độ dài còn lại sau mỗi lần xét sẽ lần lượt là ${N\over2},{N\over4},{N\over8},...,{N\over2^k}$ với $k = logN + 1$. Ta sẽ xét $k$ lần mỗi lần có độ phức tạp $O(1)$ vì vậy độ phức tạp tổng sẽ là $O(k)$ hay $O(logN)$

Bộ nhớ mở rộng: $O(1)$

# 4. Kết luận & Gợi ý mở rộng

[Code mẫu](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/submissions/1070680126/)

Một số tài liệu đọc thêm:

- https://vnoi.info/wiki/algo/basic/Binary-Search.md
- https://codeforces.com/edu/course/2/lesson/6

Bài làm thêm:
- https://codeforces.com/edu/course/2/lesson/6
> ~~Đấm hết edu codeforce là master binary search :tada:~~