Mục lục:
Định nghĩa - Tìm kiếm nhị phân có nghĩa là gì?
Một thuật toán tìm kiếm nhị phân được sử dụng để tìm vị trí của một giá trị cụ thể có trong một mảng được sắp xếp. Làm việc với nguyên tắc phân chia và chinh phục, thuật toán tìm kiếm này có thể khá nhanh, nhưng điều đáng chú ý là dữ liệu phải ở dạng được sắp xếp. Nó hoạt động bằng cách bắt đầu tìm kiếm ở giữa mảng và làm việc đi xuống nửa dưới hoặc nửa trên của chuỗi. Nếu giá trị trung bình thấp hơn giá trị đích, điều đó có nghĩa là tìm kiếm cần phải tăng cao hơn, nếu không, thì nó cần nhìn vào phần giảm dần của mảng.
Tìm kiếm nhị phân còn được gọi là tìm kiếm nửa quãng hoặc tìm kiếm logarit.
Techopedia giải thích Tìm kiếm nhị phân
Tìm kiếm nhị phân là một phương pháp nhanh chóng và hiệu quả để tìm giá trị mục tiêu cụ thể từ một tập hợp các mục được đặt hàng. Bằng cách bắt đầu ở giữa danh sách được sắp xếp, nó có thể cắt giảm một nửa không gian tìm kiếm một cách hiệu quả bằng cách xác định xem có tăng hay giảm danh sách dựa trên giá trị trung bình so với giá trị đích hay không.
Ví dụ: với giá trị mục tiêu là 8 và không gian tìm kiếm từ 1 đến 11:
- Giá trị trung bình / trung bình được tìm thấy và con trỏ được đặt ở đó, trong trường hợp này là 6.
- Mục tiêu của 8 được so sánh với 6. Vì 6 nhỏ hơn 8, mục tiêu phải ở nửa cao hơn.
- Con trỏ được chuyển đến giá trị tiếp theo (7) và được so sánh với mục tiêu. Nó nhỏ hơn, do đó con trỏ di chuyển đến giá trị cao hơn tiếp theo.
- Con trỏ bây giờ là 8. So sánh điều này với mục tiêu, nó là một kết hợp chính xác, do đó mục tiêu đã được tìm thấy.
Sử dụng tìm kiếm nhị phân, mục tiêu chỉ phải được so sánh với ba giá trị. So với thực hiện tìm kiếm tuyến tính, nó sẽ bắt đầu từ giá trị đầu tiên và di chuyển lên, cần so sánh mục tiêu với tám giá trị. Một tìm kiếm nhị phân chỉ có thể với một tập hợp dữ liệu theo thứ tự; nếu dữ liệu được sắp xếp ngẫu nhiên, thì tìm kiếm tuyến tính sẽ mang lại kết quả mọi lúc trong khi tìm kiếm nhị phân có thể bị kẹt trong một vòng lặp vô hạn.
