Lý do đằng sau giá trị trả về java.util.Collections.binarySearch là gì khi khóa không tìm thấy?

Question

Trích dẫn từ docs nó nói rằng java.util.Collections.binarySearch(List<? extends Comparable<? super T>> list, T key) lợi nhuận ...

chỉ số của khóa tìm kiếm, nếu nó được chứa trong danh sách; nếu không, (- (điểm chèn) - 1). Điểm chèn được định nghĩa là điểm mà tại đó khóa sẽ được chèn vào danh sách: chỉ mục của phần tử đầu tiên lớn hơn khóa hoặc list.size() nếu tất cả các phần tử trong danh sách đều nhỏ hơn khóa được chỉ định ...

Câu hỏi của tôi là, ý nghĩa (nếu có) có phải định lý (-(insertion point) - 1) có phải là giá trị trả về khi không tìm thấy khóa không? Tại sao không chỉ trả lại insertion point chẳng hạn?

Answer 1

Điều đầu tiên, nếu không tìm thấy phần tử, giá trị âm phải được trả lại theo tài liệu hoặc bạn không thể phân biệt giữa tìm thấy và không tìm thấy.

Ok, vậy tại sao không chỉ -insertion point? Hãy tưởng tượng nếu điểm chèn là 0 (phần tử được tìm kiếm nhỏ hơn tất cả những cái hiện có), thì logic đó sẽ vỡ - không tìm thấy sẽ trả về một số không âm. Do đó, thêm -1.

Ok, vậy tại sao không chỉ -1 luôn?

Bởi vì biết điểm chèn của một tổ chức phi trận đấu trong một danh sách được sắp xếp rất hữu ích để tìm câu trả lời cho những câu hỏi như:

phần tử tiếp theo đó là lớn hơn so với cái tôi yêu cầu là gì?

và

Có bao nhiêu yếu tố này là lớn hơn so với cái tôi (không) tìm thấy?

Và cách tìm kiếm nhị phân hoạt động, thuật toán biết chỉ mục này khi nó chấm dứt, vậy tại sao không chia sẻ khi chi phí không có gì thêm?

Answer 2

Từ cùng một tài liệu, giá trị trả lại phải> = 0 nếu khóa tồn tại. insertion point có thể bằng không nếu tất cả các phần tử lớn hơn khóa, dẫn đến giá trị trả về bằng 0 mặc dù khóa không tồn tại. Mặt khác, giá trị (-(insertion point) - 1) luôn nhỏ hơn 0.

Lưu ý rằng điều này đảm bảo rằng giá trị trả về sẽ là> = 0 nếu và chỉ khi tìm thấy khóa.

Answer 3

Đó là cách kết hợp hai trường hợp sử dụng vào một cuộc gọi phương thức. List.indexOf() và các phương thức tương tự sẽ trả về -1 khi không tìm thấy phần tử, nhưng Collections.binarySearch() tiến thêm một bước và trả về số âm cũng hữu ích khi bạn xây dựng phần tử danh sách được sắp xếp theo yếu tố.