Kahendotsing: neli valikut, kuusteist tsüklit

Tee koodis neli valikut: tsükli tingimus, hi algväärtus ja kaks uuendust. Kõrval näed, kuidas tsükkel töötab väikesel sorditud massiivil, üks läbim kord. Hinnang katsetab seda kõigil määratud pikkuseni massiividel ja kõigi sihtväärtustega; esimese nurjunud juhu saad avada ühe klõpsuga.

Näidisarvutus — Kahendotsing: neli valikut, kuusteist tsüklit

Katsetatud juhud	169
Keskpunkt kujul (lo + hi) >> 1, 32 bitti	−1 064 671 149
Keskpunkt kujul lo + ((hi − lo) >> 1)	1 082 812 499

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Kahendotsing: neli valikut, kuusteist tsüklit

Kahendotsing leiab sorditud massiivist väärtuse x, säilitades indeksite lo kuni hi vahemiku, milles x peab olemasolu korral asuma. Iga läbim loeb keskmise elemendi a[mid] ja jätab alles selle poole, kus x paikneb. Vahemik on kinnine, kui hi on viimane sellesse kuuluv indeks (lo <= hi, hi algväärtus n − 1), ning poolavatud, kui hi on esimene indeks pärast vahemikku (lo < hi, hi algväärtus n).

Mida iga sümbol tähendab

lo, hi: veel läbiotsitava vahemiku otspunktid
mid: ⌊(lo + hi)/2⌋, sellel läbimil loetav indeks
n: elementide arv; indeksid on 0 kuni n − 1
N: pikim massiiv, mida hinnang katsetab: iga n vahemikus 0 kuni N ja iga sihtväärtus, kokku (N + 1)² juhtu

Eeldab: Massiivi väärtused on erinevad, tsükkel tagastab tulemuse kohe, kui a[mid] võrdub x-iga, ning käivituses ja hinnangus kasutatakse ülempiirita täisarve. Ületäitumise tabel loobub viimasest eeldusest ja arvutab 32 bitiga nagu Java.
Ei kehti, kui: Korduvate väärtuste korral tagastavad mõlemad õiged tsüklid endiselt indeksi, millel asub x, kuid mitte tingimata esimese sellise indeksi. Esimese leidmiseks, mida vajab sorditud indeksi vahemikupäring, tuleb võrdsuse korral jätkata: kasutada poolavatud vahemikku, määrata a[mid] ≥ x korral hi = mid ning võtta tsükli lõppedes vastuseks lo.

Kuueteistkümnest tsüklist on neliteist valed ja kaks elementi paljastavad selle 🖖

Kõik neli koodis tehtavat valikut nõuavad programmeerijalt hoolt, kuigi kummagi variandi mõlemad võimalused tunduvad mõistlikud. Tulemuste all olev tabel katsetab kõiki kuutteist tsüklit iga kuni 12 elemendiga massiivi ja kõigi sihtväärtustega, kokku 169 juhul. Neist läbivad katsed kaks tsüklit. Kõik ülejäänud nurjuvad hiljemalt kaheelemendilisel massiivil ning neljateistkümnest kolmteist juba üheelemendilisel või tühjal massiivil. Kui piiriks seada 1 element, jääb alles kolm tsüklit; piiril 2 ainult kaks õiget. Piiril 256 ei nihku ühegi esimese nurjumise koht. Need väikesed juhud moodustavad täieliku katse, mitte valimi, sest tsükkel üksnes võrdleb väärtust x-iga. Iga n erinevast arvust koosnev sorditud massiiv käitub nagu 1, 3, 5 …, kus sihtväärtus asub ühes 2n + 1 võimalikust kohast, kas elemendil või kahe elemendi vahel. Hinnang proovib läbi kõik need kohad. Jon Bentley Programming Pearls võtab raskuse kokku kahe aastaarvuga: „Esimene kahendotsing avaldati 1946. aastal, kuid esimene kahendotsing, mis töötab õigesti kõigi n väärtuste korral, ilmus alles 1962. aastal.”

Kumbki kahest peaaegu õigest tsüklist jätab igas massiivis leidmata kõige rohkem ühe otsitava väärtuse 🖖

Vajuta Viimane jääb leidmata. Tingimus lo < hi koos algväärtusega hi = n − 1 peatab tsükli lo ja hi kohtumisel, kohtumiselemendist lugemata. Iga uuendus hoiab x-i vahemikus ning mid ei lange kunagi hi-le. Seetõttu saab lugemata jääda ainult element, millelt hi alustab: tsükkel leiab iga massiivi kõik elemendid peale viimase. Peegelpildi nägemiseks vajuta Loeb üle lõpu. Tingimus lo <= hi koos algväärtusega hi = n paigutab a[n]-i vahemikku ning lo jõuab selleni ainult kõigist elementidest suurema sihtväärtuse korral. Kuni 256 elemendini annavad need tsüklid vale tulemuse vastavalt 256 ja 257 juhul 66 049-st. Ainuüksi 256-elemendilisel massiivil eksivad need 0,19% sihtväärtuste korral, nii et sada juhuslikku sihtväärtust ei paljastaks tavaliselt kumbagi viga. Tühi massiiv tabab teise tsükli selle ainsal juhul, üheelemendiline massiiv esimese. JavaScriptis pääseb teine tsükkel koguni veast: a[n] on undefined, mõlemad võrdlused sellega on väärad, tsükkel määrab hi = mid − 1 ja vastab õigesti −1. Javas põhjustab sama lugemine erindi, C-s on selle käitumine määramata.

JDK õige tsükkel läks katki pärast 2³⁰ elementi 🖖

JDK tsükkel on tabeli esimene rida. See annab õige tulemuse igal juhul, mida hinnang suudab katsetada, ning just selle tsükli kirjutas Joshua Bloch klassi java.util.Arrays jaoks. Javas on lo + hi 32-bitine int; pärast väärtust 2 147 483 647 mähkub see negatiivseks arvuks. Sunile 11. mail 2004 esitatud veateates otsiti 1 100 000 000-baidise massiivi viimast elementi ja saadi ArrayIndexOutOfBoundsException: -1064671149. Ületäitumise tabel kordab otsingut ilma massiivi eraldamata. Sammul 6 on lo + hi väärtus 2 165 624 999 ning pärast mähkumist ja nihutamist on keskpunkt −1 064 671 149, täpselt veateates olnud arv. Avaldis lo + ((hi − lo) >> 1) annab samal sammul 1 082 812 499. Veateate pealkiri ütleb, et otsing nurjub massiividel, mis on suuremad kui 1<<30, ja see piir on täpne: sisesta 1 073 741 824 ning suurim lo + hi on 2³¹ − 2, mis mahub tüüpi; juba ühe elemendi lisamisel toimub sammul 31 ületäitumine. Blochi 2006. aasta kirjutise järgi varitses viga „umbes üheksa aastat” ning see leidub ka Bentley enda Programming Pearlsis tõestatud variandis. Bentley lause „määrab m-i l-i ja u keskmiseks, ümardatuna allapoole lähima täisarvuni” kehtib täisarvude, kuid mitte 32-bitiste täisarvude kohta.

Ülesanne täielikult lahendatud

Miks jäävad sõelale ainult kaks tsüklit 4 sammu
Vajuta Tsükkel takerdub, kui lo = mid. Kontroll suudab läbi proovida kuni 256 elemendiga massiivid, suuremaid mitte. Tõesta iga n-i korral, et paremalt lahtise vahemikuga tsükkel, kus lo = mid + 1, lõpetab alati töö; et sama tsükkel omistusega lo = mid takerdub iga kord, kui hi = lo + 1 ja a[lo] < x; ning mida nõuab sama arutluskäik kinnise vahemikuga tsüklilt.

Ava see ülesanne tööriistas
1. Paremalt lahtise vahemikuga tsükli keha täidetakse ainult siis, kui lo < hi. Allapoole ümardatud mid ei ole sel juhul väiksem kui lo, kuid on rangelt väiksem kui hi.
  
  $lo < hi \Rightarrow lo \leq ⌊ \frac{lo + hi}{2} ⌋ < hi$
2. Seega vähendab hi = mid väärtust hi vähemalt ühe võrra ning lo = mid + 1 suurendab väärtust lo vähemalt ühe võrra. Mõlemal juhul väheneb vahe hi − lo, mille algväärtus on n, igal iteratsioonil vähemalt ühe võrra. Alla nulli see minna ei saa, järelikult lõpetab tsükkel hiljemalt n iteratsiooni järel.
  
  $hi^{'} - lo^{'} \leq (hi - lo) - 1, n \to n - 1 \to \dots \to 0$
3. Vaatame nüüd omistust lo = mid. Kui hi = lo + 1, siis mid = ⌊(2lo + 1)/2⌋ = lo. Kui a[lo] < x, jätab uuendus lo samaks ja järgmine iteratsioon kordab eelmist. Valitud näide jõuab sellesse seisu väärtustel lo = 6 ja hi = 7, kus a[6] = 13 ning x = 14.
  
  $hi = lo + 1 : ⌊ \frac{2 lo + 1}{2} ⌋ = lo \Rightarrow lo^{'} = lo, a [6] = 13 < 14$
4. Kinnise vahemikuga tsükkel töötab seni, kuni lo <= hi, seega on lubatud ka lo = hi. Siis mid = lo = hi ning piirile väärtuse mid omistamine ei muudaks midagi. Mõlemad piiride uuendused peavad mid-ist mööduma; seda saab teha, sest a[mid] on juba loetud. Paremalt lahtine vahemik ei sisalda väärtust hi. Seal eemaldab hi = mid äsja loetud elemendi ja kõik sellest paremale jäävad elemendid, mis on tingimuse a[mid] > x põhjal välistatud. Omistus hi = mid − 1 eemaldaks lisaks elemendi a[mid − 1], kuigi just seal võib olla x.
  
  $lo = hi \Rightarrow mid = lo = hi, [lo, hi) \to [lo, mid)$
Vastus

Iga iteratsioon peab otsinguvahemikku kahandama, kõrvale võib jätta ainult indeksid, millel x asuda ei saa, ning algne vahemik peab hõlmama kogu massiivi. Tingimuse lo <= hi korral tähendab see valikuid hi = n − 1, hi = mid − 1 ja lo = mid + 1. Tingimuse lo < hi korral tuleb valida hi = n, hi = mid ja lo = mid + 1. Kontroll kinnitab neid kaht toimivat varianti kuni 256 elemendiga massiividel. Arutluskäik kehtib aga iga n-i korral, mida ükski test tõestada ei saa. 32-bitises aritmeetikas on vaja veel eeldust, et lo + hi mahub arvutüüpi; kolmas tähelepanek näitab, mis juhtub ilma selle eelduseta.

$\leq: (n - 1, mid - 1, mid + 1) <: (n, mid, mid + 1)$

Õpitee

Miks on algoritm õige

Allikad (2)

The overflow in the JDK's binary search, the nine years it went unnoticed, and Bentley's proved-correct version carrying the same line; also the source of the 1946 and 1962 dates the first insight quotes from Programming Pearls: Joshua Bloch, "Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken." Google Research Blog, 2 June 2006.
The bug report the page reproduces: java.util.Arrays.binarySearch on a 1,100,000,000-byte array, searching for its last element, throwing ArrayIndexOutOfBoundsException: -1064671149: OpenJDK bug JDK-5045582, "(coll) binarySearch() fails for size larger than 1<<30." Filed 11 May 2004 against Java 5.0, resolved (fixed in 6) 28 April 2006.

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.

Kahendotsing: neli valikut, kuusteist tsüklit

Mida iga sümbol tähendab

Kuueteistkümnest tsüklist on neliteist valed ja kaks elementi paljastavad selle 🖖

Kumbki kahest peaaegu õigest tsüklist jätab igas massiivis leidmata kõige rohkem ühe otsitava väärtuse 🖖

JDK õige tsükkel läks katki pärast 230 elementi 🖖

JDK õige tsükkel läks katki pärast 2³⁰ elementi 🖖