Хоёртын хайлт нь массив дахь элементийг олох хамгийн хялбар аргуудын нэг юм

Ихэнхдээ програмчид, тэр ч байтугай эхлэгч нар нь тодорхой тоо олоход шаардлагатай тооны дугаар байдаг тул тулгарч байдаг. Энэ цуглуулгыг массив гэж нэрлэдэг. Үүн дээр зөв элементийг олохын тулд маш олон арга зам байдаг. Гэхдээ тэдгээрийн хамгийн хялбар нь хоёртын хайлт юм. Арга гэж юу вэ? Хоёртын хайлтыг хэрхэн хийх вэ? Паскал бол ийм хөтөлбөрийг зохион байгуулах хамгийн хялбар орчин бөгөөд ингэснээр бид үүнийг ашиглахад ашиглах болно.

Нэгдүгээрт, энэ аргын давуу тал юу болохыг шинжлэх болно, тэгэхээр бид ойлгож чадна, Энэ сэдвийг судлах нь юу гэсэн үг вэ. Тиймээс, доод тал нь 100000000 элементтэй масштабтай масстай байгаа бол та тодорхой нэгийг олох хэрэгтэй. Мэдээжийн хэрэг, энэ асуудлыг энгийн шугаман хайлтаар хялбархан шийдэж болох бөгөөд бид давталтад байгаа бүх элементийг хүссэн элементтэй харьцуулахын тулд давталт ашиглана. Асуудал нь энэ санаачилгын хэрэгжилт хэтэрхий их цаг хугацаа шаарддаг явдал юм. Энгийн Pascal програмд хэд хэдэн процесс, үндсэн текстийн гурван мөрөнд та үүнийг анзаарахгүй байх болно, гэхдээ та олон тооны мөчир, сайн ажиллагаатай олон төслүүдийг эхлүүлэх үед дууссан програм хэтэрхий удаан ачаалагдах болно. Ялангуяа компьютер муу гүйцэтгэлтэй бол. Тиймээс хайлт хийх хугацааг дор хаяж хоёр удаа багасгадаг хоёртын хайлт байдаг.

Тэгэхээр энэ аргын зарчим юу вэ? Хоёртын хайлт нь ямар ч массив дотор биш харин эрэмбэлэгдсэн олон тооны тоогоор хэлэх нь зүйтэй. Дараагийн алхам бүрт массивийн дундаж элементийг авна (элементийн дугаарыг дурдав). Хэрвээ хүссэн тоо нь дундаж хэмжээнээс их байвал зүүн талд байгаа бүх зүйл нь дунджаас бага элементээс бага байж болох талтай. Эсрэгээр, хэрвээ дунджаас бага бол баруун талын тоонуудын дундаас тэдгээрийг хайж олох боломжгүй. Дараа нь бид шинэ хайлтын талбарыг сонгоно. Бүх массивын дундаж элемент нь эхний элемент байх бөгөөд хамгийн сүүлийнх нь хамгийн сүүлд байх болно. Шинэ талбайн дундаж тоо нь нийт сегментийн ¼ (хамгийн сүүлийн элемент + бүхэл массын дундаж элемент) / 2 байна. Дахин хэлэхэд, ижил үйлдэл хийгддэг - массивийн дундаж тоотой харьцуулах. Хэрвээ хүссэн утга дундажаас бага байвал баруун гар талыг нь хаяж, энэ дунд элемент олдох хүртэл ижил зүйл хийнэ.

Жишээ нь, жишээ харах хамгийн сайн арга бол хоёртын хайлтыг хэрхэн бичих вэ? Pascal энд хэн нэгэн нь тохиромжтой байдаг - хувилбар нь чухал биш юм. Энгийн програм бичье.

Энэ нь "massiv" нэртэй 1 хүртэлх массив, "niz" гэж нэрлэгдэх доод хязгаарын утгыг "хувьсагч" гэж нэрлэсэн дээд хязгаар, дунд хайлтын элемент нь "sredn"; Мөн шаардлагатай тоо бол "isk" юм.

Тиймээс эхлээд хайлтын интервалын дээд ба доод хязгаарыг оноож өгнө:

Niz: = 1;
Верш: = h + 1;

Дараа нь "доод хязгаар нь дээд хязгаараас бага" гэсэн мөчлөгийг зохион байгуулдаг.

Niz Эхлээд

Алхам бүрт сегментийг 2:

Сredn: = (niz + verh) div 2; {Див функцийг ашиглавал бид үлдсэн хэсгийг хуваах}

Бид шалгалтаа хийх бүрдээ. Хэрвээ дундаж нь хүссэн элементтэй тэнцүү бол бид хүссэн элементийн аль хэдийн олддог тул мөчлөгийг тасалдуулдаг:

Түүний sredn = isk дараа нь завсарлагаа;

Хэрэв массивын дундаж элемент нь бидний хайж байгаагаас их бол бид зүүн талыг хаяна, өөрөөр хэлбэл дунд элементийг дээд хязгаар руу шилжүүлнэ:

Хэрэв массив [sredn]> isk дараа нь verh: = sredn;

Харин эсрэгээрээ, бид үүнийг доод хязгаар болгож байна:

Өөрөөр хэлбэл: = sredn;
Төгсгөл;

Энэ нь хөтөлбөрт байх болно.

Практикт хоёртын арга хэрхэн харагдахыг судлах. Бид ийм масстай: 1, 3, 5, 7, 10, 12, 18, 12 тоог хайж олох хэрэгтэй.

Нийтдээ 7 элементтэй, дундаж нь дөрөв, түүний үнэ 7 байна.

12-аас 7-аас их бол элемент 1,3 ба 5-ийг хасаж болно. Дараа нь бид 4 дугаар үлдсэн, 4/2 үлдсэн нь 2 байна. Тэгэхээр шинэ дунд элемент нь 10 байна.

12-аас 10-аас дээш бол бид 7-ыг хасна. Зөвхөн 10, 12, 18-р үлдэнэ.

Энд дунд элемент 12 байна, энэ нь шаардлагатай тоо юм. Ажил дууссан - 12 дугаартай байна.