Tìm kiếm nhị phân (Binary Search) trong ListView Android

Binary Search trong ArrayList

Collections.binarySearch() tìm kiếm phần tử trong list **đã sắp xếp** với độ phức tạp O(log n). Nhanh hơn tìm kiếm tuyến tính O(n).

Điều kiện bắt buộc

• List phải được sắp xếp (Collections.sort()) trước khi binarySearch.
• Phần tử phải implements Comparable hoặc cung cấp Comparator.

MainActivity.java

public class MainActivity extends AppCompatActivity {
    private EditText edtName;
    private ListView listView;
    private ArrayAdapter<String> adapter;
    private ArrayList<String> dataList = new ArrayList<>();
    private Set<String> nameSet = new HashSet<>();

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        edtName = findViewById(R.id.name);
        listView = findViewById(R.id.listView);
        adapter = new ArrayAdapter<>(this, android.R.layout.simple_list_item_1, dataList);
        listView.setAdapter(adapter);

        findViewById(R.id.save).setOnClickListener(v -> addAndSearch());
        findViewById(R.id.refresh).setOnClickListener(v -> adapter.notifyDataSetChanged());
    }

    private void addAndSearch() {
        String name = edtName.getText().toString().trim();
        if (name.isEmpty()) {
            edtName.setError("Nhập tên");
            return;
        }

        nameSet.add(name);
        edtName.setText("");

        dataList.clear();
        dataList.addAll(nameSet);
        Collections.sort(dataList); // BẮT BUỘC sắp xếp trước binarySearch

        // Tìm "sairam" trong list đã sort
        int index = Collections.binarySearch(dataList, "sairam");
        
        if (index >= 0) {
            // Tìm thấy: index là vị trí
            Toast.makeText(this, "Tìm thấy 'sairam' tại vị trí: " + index, Toast.LENGTH_LONG).show();
            
            // Ví dụ: thay thế tất cả phần tử bằng "sairam" (demo)
            Collections.fill(dataList, "sairam");
        } else {
            // Không tìm thấy: (-(insertion point) - 1)
            int insertPos = -index - 1;
            Toast.makeText(this, "'sairam' chưa có. Sẽ chèn tại vị trí: " + insertPos, Toast.LENGTH_LONG).show();
        }

        adapter.notifyDataSetChanged();
    }
}

Giải thích kết quả binarySearch

Kết quả demo

Nhập "sairam" → tìm thấy → Collections.fill() thay tất cả thành "sairam".

Lưu ý quan trọng

• Phải sort trước: binarySearch trên list chưa sort cho kết quả sai.
• Với object tùy chỉnh: dùng binarySearch(list, key, comparator).
• ListView không phù hợp cho dữ liệu lớn (>1000 item). Nên dùng RecyclerView + DiffUtil.
• Tìm kiếm thực tế: dùng SearchView + Filterable adapter hoặc Room + FTS.

Binary Search vs Linear Search