Бұл не?
Сабақтың тақырыбы — «Іздеу: сызықтық және екілік». Талдап көрейік. Қағаз сөздіктен сөз іздегенде, сен бірінші беттен бастап парақтамайсың, ортасынан бір жерден ашып, керекті сөз әрі қарай ма, әлде бұрын ба — соған қарайсың. Екілік іздеу осылай жұмыс істейді. Ал сөредегі кітаптар ретсіз тұрса, оларды бір-бірлеп тексеру ғана қалады — бұл сызықтық іздеу.
Бұл не үшін керек?
Іздеу — компьютердің ең жиі кездесетін міндеттерінің бірі: телефоннан контакт табу, интернет-дүкендегі миллиондаған тауардың ішінен біреуін табу, банктің немесе аурухананың дерекқорынан қажетті жазбаны табу. Гугл сияқты іздеу жүйелері мен дата-орталықтардағы дерекқорлар орасан зор ақпарат көлемін дәл қарапайым іріктеуді емес, ақылды алгоритмдерді пайдаланатындықтан игереді. Жасанды интеллект іздеу кодын бір секундта жаза алады, бірақ қолайлы алгоритмді таңдау, бағдарлама миллион жазбада неге баяулайтынын түсіну және оны ыңғайсыз жағдайларда тексеру — адамның жұмысы. Қадамдар санының қаншалықты тез өсетінін түсіну инженерді кодты жай ғана көшіретін адамнан ажыратады.
Бұл қалай жұмыс істейді?
Деректер тізімде жатады, және әр элементтің нөмірі — индексі болады; Питонда индекстер нөлден басталады. Сызықтық іздеу элементтерді кезекпен тексереді және кез келген тізіммен жұмыс істейді, бірақ ең нашар жағдайда тізімде қанша элемент болса, сонша салыстыру жасайды. Екілік іздеу тек реттелген тізіммен жұмыс істейді: ол ортаңғы элементке қарайды да, ол ізделетіннен кіші болса, бүкіл сол жақ жартысын, ал үлкен болса — оң жақ жартысын алып тастайды. Әр салыстыру іздеу аймағын екіге бөледі, сондықтан миллион элементтің арасында да шамамен жиырма қадам жеткілікті.
Аздап тарих
Екілік іздеу идеясын сонау бір мың тоғыз жүз қырық алтыншы жылы алғашқы электрондық компьютерлерді жасаушылардың бірі Джон Мокли сипаттаған. Идея қарапайым көрінеді, бірақ оны қатесіз жазу таңқаларлықтай қиын: белгілі бағдарламашы Дональд Кнут жарияланған алғашқы толық дұрыс нұсқасы көп жылдан кейін ғана пайда болғанын атап өткен. Ал Джава тілінің стандартты кітапханасындағы екілік іздеудегі қатені шыққаннан кейін бірнеше жыл өткен соң ғана тапты.
Практикада не істейміз?
Ал енді практикалық тапсырманы орындап көрейік. Алдыңда индекстері нөлден он төртке дейінгі он бес карточка тұр; олардағы сандар жасырын, бірақ олардың өсу ретімен орналасқанын білесің. Жетпіс саны жасырылған, оны төрт карточкадан артық ашпай табу керек. Сол жақтан рет-ретімен ашу — үлгермеудің сенімді жолы, сондықтан әр жолы өзіңнен сұра: іздеу аймағының ортасында қай карточка тұр және оның санын жетпіспен салыстырудан не шығады? Әр ашқаннан кейін анық сәйкес келмейтін жартысын алып таста да, аймақтың қалай тарылып жатқанына қара. Егер бірдеңе түсініксіз болып қалса — ештеңе етпейді, менен кез келген нәрсені сұра, мен жауап беремін. Уайымдама.