# Tìm kiếm nhị phân --- **Tác giả : [Dương Nguyên Khánh](https://github.com/kduongnguyen07)** ###### tags:`Algorithm`,`Search` # **Mở đầu** ### Khái niệm Là một cách tìm kiếm nhanh trong 1 mảng đã sắp xếp ([Xem thêm về sắp xếp](https://hackmd.io/@lck7prime/sort)) #### Ý tưởng ``` Ta có thể dễ dàng hiểu được ý tưởng của thuật toán tìm kiếm nhị phân. Đúng như tên gọi, thuật toán sẽ liên tục chia không gian tìm kiếm thành hai nửa và loại một nửa đi. Thuật toán có thể trình bày như sau: Ta duy trì một không gian tìm kiếm S là một dãy con các giá trị có thể là kết quả (ở đây là chỉ số các phần tử trong A). Ban đầu,không gian tìm kiếm là toàn bộ các chỉ số của mảng S=1,…,n với n là chỉ số phần tử cuối cùng của A Ở mỗi bước, thuật toán so sánh giá trị cần tìm với phần tử có chỉ số là trung vị trong không gian tìm kiếm. Dựa trên sự so sánh đó, cộng thêm việc ta biết dãy A có thứ tự, ta có thể loại một nửa số phần tử của S Lặp đi lặp lại quá trình,ta sẽ được một không gian bao gồm một phần tử Khi đó, nếu phần tử duy nhất đó bằng với giá trị cần tìm x thì đó là nghiệm của bài toán, nếu không thì bài toán vô nghiệm ``` [Minh hoạ](https://www.cs.usfca.edu/~galles/visualization/Search.html) ##### Cài đặt ```C++ int binary_search(int A[], int sizeA, int target) { int lo = 1, hi = sizeA; while (lo <= hi) { int mid = lo + (hi - lo)/2; if (A[mid] == target) return mid; else if (A[mid] < target) lo = mid+1; else hi = mid-1; } // không tìm thấy giá trị target trong mảng A return -1; } ``` Nhận xét : Độ chính xác cao và dễ cài đặt ## STL Binary Search Tìm kiếm nhị phân trong thư viện chuẩn STL C++ Standard Template Library đã cài đặt sẵn tìm kiếm nhị phân bằng các hàm lower_bound, upper_bound, binary_search, equal_range