package utility

import "sort"

// 二分查找（会将切片 a 排为升序）
//
// 找到返回 true，未找到返回 false
func BinarySearch(a []int, x int) bool {
	if !sort.IntsAreSorted(a) {
		sort.Ints(a)
	}

	l, r := 0, len(a)-1

	for l <= r {
		m := (l + r) / 2
		if a[m] == x {
			return true
		}
		// x 在左边
		if x < a[m] {
			r = m - 1
		} else {
			l = m + 1
		}
	}

	return false
}
