Tìm kiếm nhị phân

**Tìm kiếm nhị phân** xét phần tử giữa vùng đang tìm. Trong bài này dãy đã được sắp xếp **tăng dần**. Nếu giá trị cần tìm bằng giá trị giữa thì tìm thấy; nếu nhỏ hơn thì chỉ cần tìm nửa trước, nếu lớn hơn thì chỉ cần tìm nửa sau. Hai nửa mới không gồm phần tử giữa vừa xét. Nhờ thứ tự tăng dần, ta biết những phần tử ở phía bị bỏ không thể là giá trị cần tìm. Không dùng cách loại một nửa như vậy trên dãy chưa sắp xếp: có thể bỏ nhầm phần tử cần tìm. Giữ nguyên vị trí đánh số theo dãy ban đầu. Sau khi thu hẹp, không đánh lại từ 1 cho phần còn lại, vì đầu ra cần chỉ đúng vị trí trong toàn dãy.

Ban đầu vùng tìm kiếm là toàn bộ dãy. Vị trí giữa được tính bằng phần nguyên của (vị trí đầu + vị trí cuối)/2. Vì các vị trí là số dương, chẳng hạn 7.5 lấy phần nguyên là 7. Vùng từ vị trí 6 đến 9 có giữa là vị trí 7, vì (6+9)/2 = 7.5. Nửa trước gồm vị trí 6; nửa sau gồm vị trí 8 và 9. Vị trí 7 không nằm trong hai nửa mới. Lặp lại việc xét giữa và chọn nửa thích hợp. Nếu vùng không còn phần tử, thông báo không tìm thấy; không cố đọc một vị trí nằm ngoài dãy.

Viết chín số 6, 12, 18, 25, 31, 44, 57, 63, 80 lên thẻ và giữ thứ tự tăng dần. Lập bảng gồm vùng đầu–cuối, vị trí giữa, giá trị giữa và vùng mới. Thử tìm 60: | Lần xét | Vùng | Giữa | Giá trị | Kết quả | |---|---|---|---|---| | 1 | 1–9 | 5 | 31 | Giữ 6–9 | | 2 | 6–9 | 7 | 57 | Giữ 8–9 | | 3 | 8–9 | 8 | 63 | Giữ 8–7: vùng rỗng | Sau lần thứ ba, vị trí đầu lớn hơn vị trí cuối nên không còn phần tử để tìm. Kết luận không tìm thấy 60. Kiểm mỗi vùng mới đã bỏ phần tử giữa; không chỉ thu vùng mà giữ nguyên điểm giữa mãi. Sắp xếp giúp tìm kiếm nhị phân loại bớt dữ liệu. Tuy nhiên không phải mọi lần tìm đều ít bước hơn tuần tự: với cùng dãy, tìm 6 bằng tuần tự chỉ cần một lần xét, còn nhị phân cần ba. Việc so sánh này chỉ đếm các lần tìm, chưa tính công sắp xếp dãy ban đầu.