Хоёртын хайлт ба Шугаман хайлт
Дараалсан хайлт гэж нэрлэгддэг шугаман хайлт нь хамгийн энгийн хайлтын алгоритм юм. Энэ нь жагсаалтын элемент бүрийг шалгах замаар жагсаалтаас тодорхой утгыг хайдаг. Хоёртын хайлт нь эрэмбэлэгдсэн жагсаалтад заасан утгыг олоход хэрэглэгддэг арга юм. Хоёртын хайлтын арга нь шалгасан элементийн тоог хоёр дахин багасгаж (давталт бүрт) жагсаалтаас тухайн зүйлийн байршлыг олоход зарцуулагдах хугацааг багасгадаг.
Шугаман хайлт гэж юу вэ?
Шугаман хайлт нь хамгийн энгийн хайлтын арга бөгөөд жагсаалтын элемент бүрийг заасан элементийг олох хүртэл дараалан шалгадаг. Шугаман хайлтын аргын оролт нь дараалал (массив, цуглуулга эсвэл мөр гэх мэт) бөгөөд хайх шаардлагатай зүйл юм. Хэрэв заасан зүйл нь өгөгдсөн дарааллын дотор байвал гаралт үнэн, дараалалд байхгүй бол худал байна. Энэ арга нь заасан зүйл олдох хүртэл жагсаалтын бүх зүйлийг шалгадаг тул хамгийн муу тохиолдолд шаардлагатай элементийг олохын өмнө жагсаалтын бүх элементүүдийг шалгана. Шугаман хайлтын нарийн төвөгтэй байдал нь o(n). Тиймээс үүнийг том жагсаалтаас элементүүдийг хайхад ашиглахад хэтэрхий удаан гэж үздэг. Гэхдээ энэ нь маш энгийн бөгөөд хэрэгжүүлэхэд хялбар.
Хоёртын хайлт гэж юу вэ?
Хоёртын хайлт нь мөн эрэмбэлэгдсэн жагсаалтаас заасан зүйлийн байршлыг олоход хэрэглэгддэг арга юм. Энэ арга нь хайсан элементийг жагсаалтын дундах элементүүдтэй харьцуулж эхэлдэг. Хэрэв харьцуулалт нь хоёр элемент тэнцүү болохыг тогтоовол арга нь зогсох ба элементийн байрлалыг буцаана. Хэрэв хайсан элемент нь дунд элементээс их байвал эрэмбэлэгдсэн жагсаалтын зөвхөн доод талыг ашиглан аргыг дахин эхлүүлнэ. Хэрэв хайсан элемент нь дунд элементээс бага байвал эрэмбэлэгдсэн жагсаалтын зөвхөн дээд талыг ашиглан аргыг дахин эхлүүлнэ. Хэрэв хайсан элемент жагсаалтад байхгүй бол арга нь үүнийг харуулсан өвөрмөц утгыг буцаана. Тиймээс хоёртын хайлтын арга нь харьцуулалтын үр дүнгээс хамааран харьцуулсан элементүүдийн тоог хоёр дахин бууруулдаг (давталт бүрт). Иймээс хоёртын хайлт нь логарифмын хугацаанд ажилласнаар o(log n) тохиолдлын дундаж гүйцэтгэлийг бий болгодог.
Хоёртын хайлт болон шугаман хайлт хоёрын ялгаа юу вэ?
Шугаман хайлт болон хоёртын хайлт хоёулаа хайлтын аргууд боловч хэд хэдэн ялгаатай байдаг. Хоёртын хайлт нь эрэмбэлэгдсэн жагсаалтууд дээр ажилладаг бол давхаргын хайлт нь эрэмбэлэгдээгүй жагсаалтууд дээр бас ажиллах боломжтой. Жагсаалтыг эрэмбэлэх нь ерөнхийдөө n log n-ийн дундаж тохиолдлын нарийн төвөгтэй байдалтай байна. Шугаман хайлт нь хоёртын хайлтаас хялбар бөгөөд хэрэгжүүлэхэд хялбар юм. Гэхдээ шугаман хайлт нь o(n) дундаж кейс гүйцэтгэлийн улмаас том жагсаалтад ашиглахад хэтэрхий удаан байдаг. Нөгөө талаас, хоёртын хайлт нь том жагсаалтад ашиглагдах илүү үр дүнтэй арга гэж тооцогддог. Гэхдээ хоёртын хайлтыг хэрэгжүүлэх нь нэлээд төвөгтэй байж болох бөгөөд судалгаагаар хоёртын хайлтын үнэн зөв кодыг хорин номны таваас л олж болохыг харуулсан.
