Ինչպես է աշխատում բինար որոնման ալգորիթմը?

Իրականացնելով սորտավորված զանգվածի վերլուծություն և որոնման միջակայքը շարունակաբար կեսերով բաժանելով, բինար որոնումը աշխատում է:

1. Սկիզբ: Հրապարակվում են որոնման միջակայքի ձախ և աջ սահմանները (հաճախ զանգվածի սկզբնամասը և վերջը):
2. Համեմատություն: Հաշվարկվում է միջակայքի միջնամասի ինդեքսը: Այդ ինդեքսում գտնվող արժեքը համեմատվում է որոնվող տարրին:
3. Միջակայքի կրճատում:
   • Եթե միջնամասի արժեքը համընկնում է որոնվողի հետ, տարրն գտնվեց:
   • Եթե միջնամասի արժեքը մեծ է որոնվողից, որոնումը շարունակվում է միջակայքի ձախ կեսում: Դասավորության աջ սահմանը տեղափոխվում է միջնամաս - 1:
   • Եթե միջնամասի արժեքը փոքր է որոնվողից, որոնումը շարունակվում է միջակայքի աջ կեսում: Դասավորության ձախ սահմանը տեղափոխվում է միջնամաս + 1:
4. Կրկնում: Քայլեր 2 և 3 կրկնվում են մինչև տարրն գտնվի կամ միջակայքը դատարկ լինի:

Ալգորիթմի բարդությունը կազմում է O(log n), ինչը շատ ավելի արդյունավետ է, քան գծային որոնումը մեծ զանգվածների համար:

def binary_search(arr, target):
    """
    Երկկողմ որոնման իրականացում:
    Տվյալը՝ սորտավորված զանգված և որոնվող արժեք:
    Վերադարձնում է տարրի ինդեքսը կամ -1, եթե չի գտնվել:
    """
    ձախ, աջ = 0, len(arr) - 1

    while ձախ <= աջ:
        միջ = (ձախ + աջ) // 2  # Միջին ինդեքսի հաշվարկ
        միջին_արժեք = arr[միջ]      # Միջին արժեքը

        if միջին_արժեք == target:
            return միջ  # Տարրն գտնվեց
        elif միջին_արժեք < target:
            ձախ = միջ + 1  # Հետազոտությունը աջ կողմում
        else: # միջին_արժեք > target
            աջ = միջ - 1 # Հետազոտությունը ձախ կողմում

    return -1 # Տարրն չի գտնվել