`Collections.binarySearch` în Java

Caută rapid o valoare într-o listă sortată, prin înjumătățiri. Returnează poziția sau un număr negativ care arată unde ar trebui inserată.

Sintaxă

static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)
static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)

Ce face `Collections.binarySearch`

Căutarea binară compară valoarea cu elementul din mijloc și continuă doar în jumătatea potrivită. Pentru o listă de un milion de elemente sunt de ajuns cam 20 de comparații. Condiția obligatorie: lista trebuie să fie sortată (crescător sau după același comparator). Pe o listă nesortată, rezultatul nu are sens.

Dacă valoarea este găsită, metoda returnează poziția ei. Dacă nu, returnează -(punctInserare) - 1, un număr negativ. Poziția unde ar trebui inserată valoarea ca lista să rămână sortată se obține cu -rezultat - 1.

Parametri

Parametru	Descriere
`list`	Lista sortată.
`key`	Valoarea căutată.
`c`	Comparatorul cu care a fost sortată lista.

Ce returnează

Poziția (≥ 0) sau -(punctInserare) - 1.

Exemple

Exemplul 1: Căutare și poziția de inserare

import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> coduri = List.of(100, 205, 310, 480, 555, 700);
        System.out.println("310 la poziția " + Collections.binarySearch(coduri, 310));
        int r = Collections.binarySearch(coduri, 400);
        System.out.println("400: rezultat " + r + ", s-ar insera la poziția " + (-r - 1));
    }
}

Rezultat

310 la poziția 2
400: rezultat -4, s-ar insera la poziția 3

Exemplul 2: Inserare care păstrează lista sortată

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> nume = new ArrayList<>(List.of("Ana", "Elena", "Mihai"));
        for (String nou : new String[] {"Bogdan", "Radu", "Ana"}) {
            int poz = Collections.binarySearch(nume, nou);
            if (poz >= 0) {
                System.out.println(nou + " există deja");
            } else {
                nume.add(-poz - 1, nou);
            }
        }
        System.out.println(nume);
    }
}