Бинарный происк - EcsFlash/DataTypes GitHub Wiki

Даже Сережа Шойгуев знает как работает бинарный поиск, а ты?

Красивая анимация

gif

Псевдокод

НЕ рекурсивный вариант

func BinarySearch(a []int, x int) int {
	start := 0
	end := len(a) - 1
	for start <= end {
		mid := (start + end) / 2
		if a[mid] == x {
			return mid
		} else if a[mid] < x {
			start = mid + 1
		} else if a[mid] > x {
			end = mid - 1
		}
	}
	return -1
}

Рекурсивный вариант

func BinarySearchRecursive(arr []int, x int, start, end int) int {
    if start > end {
        return -1
    }
    mid := start + (end - start) / 2
    if arr[mid] == x {
        return mid
    } else if arr[mid] < x {
        return BinarySearchRecursive(arr, x, mid+1, end)
    } else {
        return BinarySearchRecursive(arr, x, start, mid-1)
    }
}

image