Shpjegoni pse ky algoritëm funksionon.
def binary_search(list, target): më poshtë = 0 më lart = len(list) - 1 ndërsa më poshtë <= më lart: mes = (më poshtë + më lart) // 2 # Pjesa e katit parashikojnë = listë[mid] nëse parashikojnë == target: ktheni mes nëse parashikojnë > target: më lart = mes - 1 tjetër: më poshtë = mes + 1 ktheni Asnjë
Ky algoritëm funksionon duke përdorur një qasje të ndarë dhe të pushtuar. Ai fillon duke ndarë listën e dhënë në dy pjesë dhe gjen një pozicion të rregulluar duke e gjysmuar vazhdimisht listën derisa të gjendet elementi i synuar. Kjo qasje është e dobishme sepse redukton shumë numrin e krahasimeve të kërkuara për të gjetur vlerën e synuar. Nëse elementi nuk gjendet, kufijtë e sipërm dhe të poshtëm për kërkim bëhen të barabartë, që do të thotë se elementi nuk ekziston në listë. Prandaj, algoritmi është i garantuar të gjejë objektivin (nëse ekziston) ose të kthejë asnjë nëse nuk ekziston.