Хоёртын хайлт нь өгөгдлийн бүтцийг ашиглан энгийн хайх аргаас илүү хурдан хайх арга юм. Бид өгөгдлийг тодорхой шинж чанар, зүй тогтол, дарааллын дагуу бүтэцлэх нь Зарим нэг үйлдлүүдийг хийхгүй байж болох давуу талыг үүсгэдэг. Үүний нэг жишээ нь хоёртын хайлтын алгоритм юм.
Хоёртын хайлтыг зөвхөн ямарваа нэгэн шинж тэмдгээр өсөхөөр эсвэл буурахаар эрэмбэлсэн Өгөгдөл дээр хэрэгжүүлж болдог. Яагаад гэвэл энэхүү алгоритм нь Тухайн өгөгдлүүдийг эрэмбэлсэн гэж итгэн бүх элементийг 1 1-ээр нь шалгахгүй Байгаа нь түүний хурдан байгаагийн нууц юм. Үндсэн арга. Өсөхөөр эрэмбэлэгдсэн арайийн эхний болон төгсгөлийн индексийг хадгалж авч. Яг голын индексийг хайж байгаа тоотойгоо жишиж тэмцэж байвал тухайн Индексийг буцаана. Харин үл тэмцэж байгаа тохиолдолд. Хайж байгаа. тооноос бага байна уу их байна уу гэдгийг жишиж .Их байвал иксто голын элементээс дээшээ байгаа нь баталгаатай гэж үзнэ. Харин бага байвал мөн адил иксто голын элементээс доошоо байгаа нь баталгаатай гэж үзнэ. Ингэснээр баталгаатай гэж үзсэн хэсгээ тасдаж аваад түрүүний аргаар дахин хайна. Үүнийг баталгаатай гэж үзэж байгаа хэсэг нэг ширхэг элементтэй болтол үргэлжлүүлж Тэр хүртэл хайж байгаа. Та олдоогүй бол тухайн хүснэгтэд хайж байгаатоо байхгүй байна гэж үзнэ.
Python code
Python code
def binary_search(arr, x):
low = 0
high = len(arr) – 1
mid = 0
while low <= high:
mid = (high + low) // 2
if arr[mid] < x:
low = mid + 1
elif arr[mid] > x:
high = mid – 1
else:
return mid
return –1
arr = [ 2, 3, 4, 10, 40 ]
x = 10
result = binary_search(arr, x)
if result != –1:
print(“Element is present at index”, str(result))
else:
print(“Element is not present in array”)
Энэ нь зөвхөн тодорхой нэг тоог хайхад бус Хайж байгаа өгөгдлийн зүй тогтлоос хамааран. Олон өөр зорилгоор ашиглаж болох арга юм. Учир нь хоёртын хайлтын арга нь өөрөө Хуваан эзлэх алгоритмаас гаралтай юм. Энгийн хайх аргаар бид O(n) хугацаанд хайдаг бол. Хоёртын хайлтын аргаар O(log n) хугацаанд хайж олж болно.
