List.binarySearch în Kotlin

fun <T : Comparable<T>> List<T?>.binarySearch(element: T?, deLa: Int = 0, panaLa: Int = size): Int
fun <T> List<T>.binarySearchBy(cheie: K?, selector: (T) -> K?): Int

Ce face List.binarySearch

Căutarea binară împarte lista în două la fiecare pas, deci găsește un element între un milion în aproximativ 20 de pași. Condiția obligatorie: lista trebuie să fie sortată crescător (după același criteriu folosit la căutare). Pe o listă nesortată, rezultatul nu are sens.

Dacă elementul există, rezultatul este poziția lui. Dacă nu există, rezultatul este negativ: -(punctDeInserare) - 1, unde punctDeInserare este poziția la care ar trebui pus ca lista să rămână sortată. Deci -rezultat - 1 îți dă acea poziție.

binarySearchBy(cheie) { it.proprietate } caută după o proprietate a obiectelor (lista trebuie sortată după aceeași proprietate).

Parametri

Parametru	Descriere
element	Valoarea căutată.
deLa, panaLa	Opțional: caută doar în această porțiune (panaLa exclus).

Ce returnează

Poziția elementului (≥ 0) sau -(punctDeInserare) - 1 (negativ).

Exemple

Exemplul 1: Găsit și negăsit

Pentru 50 rezultatul este -5: ar trebui inserat la poziția 4 (-(-5) - 1).

fun main() {
    val praguri = listOf(10, 20, 35, 40, 60, 75)
    println(praguri.binarySearch(40))
    val r = praguri.binarySearch(50)
    println(r)
    println("50 ar intra pe poziția ${-r - 1}")
}

Rezultat

3
-5
50 ar intra pe poziția 4

Exemplul 2: Inserare păstrând ordinea

Folosim rezultatul negativ ca să inserăm fiecare nume nou la locul lui alfabetic.

fun main() {
    val nume = mutableListOf("Ana", "Dan", "Maria")
    for (nou in listOf("Bogdan", "Zoe", "Carmen")) {
        val r = nume.binarySearch(nou)
        val poz = if (r >= 0) r else -r - 1
        nume.add(poz, nou)
    }
    println(nume)
}

Rezultat

[Ana, Bogdan, Carmen, Dan, Maria, Zoe]

Exemplul 3: Căutare după o proprietate

Lista este sortată după cod; binarySearchBy compară codurile.

data class Judet(val cod: String, val nume: String)

fun main() {
    val judete = listOf(Judet("AB", "Alba"), Judet("BV", "Brașov"), Judet("CJ", "Cluj"), Judet("IS", "Iași"))
    val i = judete.binarySearchBy("CJ") { it.cod }
    println("$i -> ${judete[i].nume}")
    println(judete.binarySearchBy("SV") { it.cod })
}

Rezultat

2 -> Cluj
-5

Greșeli frecvente

• Folosești binarySearch pe o listă nesortată: poate întoarce un rezultat negativ deși elementul există. Sortează întâi sau folosește indexOf.
• Verifici doar rezultat == -1 ca „negăsit”: orice număr negativ înseamnă negăsit.

Comenzi înrudite

• Iterable.contains: contains (operatorul in) verifică dacă un element există; indexOf dă poziția primei apariții sau -1.
• Iterable.sorted: Întoarce o listă nouă cu elementele în ordine crescătoare (sorted) sau descrescătoare (sortedDescending).
• MutableList.sort: Sortează chiar lista modificabilă (pe loc), crescător, descrescător sau după un câmp; nu întoarce nimic.
• MutableList.add: Adaugă un element la finalul listei sau la o poziție dată; addAll adaugă mai multe elemente deodată.