Анықтау ойыны

Бір тапсырмаға арналған әртүрлі алгоритмдердің тиімділігі әртүрлі болуы мүмкін екендігі туралы түсінік беру үшін кішкене ойын ойнайық. Компьютер кездейсоқ 1-ден 15-ке дейінгі бүтін санды таңдайды. Сіз компьютер нөмірін тапқанша сандарды болжай бересіз және компьютер әр уақытта сіздің болжамыңыз тым жоғары немесе тым төмен болғанын айтады:

Нөмірді тапқаннан кейін, қай санды табу керектігін шешкен кезде қандай техниканы қолданғаныңыз туралы ойланыңыз.

Сіз дұрыс санды тапқанша 1 санын болжап, содан кейін 2 санын, содан кейін 3, содан кейін 4 және т.б. Біз бұл тәсілді сызықтық іздеу деп атаймыз, өйткені сіз барлық сандарды қатарға қойылғандай болжайсыз. Бұл жұмыс істейтін еді. Бірақ сізге ең көп болжам қажет болуы мүмкін? Егер компьютер 15-ті таңдаса, сізге 15 болжам қажет болады. Екінші жағынан, сіз шынымен сәттілікке ие болуыңыз мүмкін және бұл компьютер 1-ді таңдаған кезде пайда болады және сіз бірінші нөмірді аласаңыз. Орташа ше? Егер компьютер 1-ден 15-ке дейінгі кез-келген санды бірдей таңдаса, онда сізге орташа есеппен 8 болжам қажет болады.

Бірақ сіз 1, 2, 3, 4-ті болжаудан гөрі тиімді нәрсе жасай аласыз ... рас қой? Компьютер сізге болжамның тым төмен, тым жоғары немесе дұрыс екенін білетіндіктен, сіз 8-ді болжаудан бастай аласыз. Егер компьютер таңдаған сан 8-ден аз болса, онда 8-нің тым үлкен екенін білетіндіктен, сіз 8-ден 15-ке дейінгі барлық сандарды одан әрі қарастырудан алып тастай аласыз. Егер компьютер таңдаған сан 8-ден үлкен болса, онда сіз 1-ден 8-ге дейін алып тастай аласыз. Қалай болғанда да, сіз сандардың жартысын алып тастай аласыз. Келесі болжам бойынша қалған сандардың жартысын алып тастаңыз. Әрқашан қалған сандардың жартысын қоспай жалғастырыңыз.

Біз бұл тәсілді екіге бөлу деп атаймыз екілік іздеу және компьютерді таңдаған 1-ден 15-ке дейінгі Сан қандай болса да, сіз осы әдісті қолдана отырып, 4-тен аспайтын санды таба аласыз.

Мұнда 1-ден 300\ - ге дейінгі санды болжауға тырысыңыз. Сізге 9 болжамнан артық болжам қажет емес.

Бұл жолы нөмірді табу үшін сізге қанша болжам қажет болды? Неліктен сізге ешқашан 9 болжамнан артық болжам қажет емес? (Математикалық түсініктеме бере аласыз ба)?

Біз екілік іздеуге ораламыз және оны JavaScript массивіндегі элементті тиімді іздеу үшін қалай пайдалануға болатынын көреміз. Бірақ алдымен күрделі тапсырма үшін алгоритмді қарастырайық.

Бұл мазмұн ынтымақтастықтың нәтижесі Дартмут компьютерлік ғылымы профессорлар [Томас Кормен](http://www.cs.dartmouth.edu / ~thc/) және [Дэвин Бэлком](http://www.cs.dartmouth.edu / ~devin/), сонымен қатар Хан академиясының компьютерлік оқу бағдарламасы бойынша тобы. Мазмұн лицензияланған CC-BY-NC-SA.