جستجوی دودویی

الگوریتم جستجوی دودویی تکنیکی است برای یافتن یک مقدار عددی از میان مجموعه‌ای از اعداد مرتب. این متد محدودهٔ جستجو را در هر مرحله به نصف کاهش می‌دهد، بنابراین هدف مورد نظر یا به زودی پیدا می‌شود یا مشخص می‌شود که مقدار مورد جستجو در فهرست وجود ندارد.

جستجوی دودویی فقط در آرایه‌های مرتب استفاده می‌شود. در این روش عنصر مورد نظر با خانه وسط آرایه مقایسه می‌شود اگر با این خانه برابر بود جستجو تمام می‌شود اگر عنصر مورد جستجو از خانه وسط بزرگتر بود جستجو در بخش بالایی آرایه و در غیر این صورت جستجو در بخش پایینی آرایه انجام می‌شود (فرض کرده‌ایم آرایه به صورت صعودی مرتب شده‌است) این رویه تا یافتن عنصر مورد نظر یا بررسی کل خانه‌های آرایه ادامه می‌یابد.

مثال:

package main

import (
    "errors"
    "fmt"
)

func main() {
    list := []int{1, 2, 3, 6, 7, 8, 10, 12, 15, 16, 17, 18, 19, 22, 23, 24, 25, 29, 33}
    index, err := binary_search(list, 10)
    if err != nil {
        fmt.Println(err.Error())
        return
    }
    fmt.Printf("index: %d", index)
}

func binary_search(list []int, item int) (int, error) {
    low := 0
    hight := len(list) - 1
    for low <= hight {
        mid := (low + hight) / 2
        guess := list[mid]
        if guess == item {
            return mid, nil
        } else if guess < item {
            low = hight - mid
        } else {
            hight = mid + 1
        }
    }
    return 0, errors.New("number not found")
}

#binary_search

@Syntax_fa