面试题 / 算法

二分法查找

百度百科： 二分法查找适用于数据量较大时，但是数据需要先排好顺序

常见的必考题，而且经常要求手写，甚至需要会写多种形式

时间复杂度 O(log2n)

循环

func binarySearch(arr []int,k int) int {

	low,high := 0,len(arr)-1
	for low <= high {
		mid := (low + high) >> 1
		if k > arr[mid] {
			low = mid + 1
		} else if k < arr[mid] {
			high = mid - 1
		} else {
			return mid
		}
	}
	return 0
}

递归


func Search(arr []int,k int) int {
	return binarySearch(arr,k,0,len(arr)-1)
}

func binarySearch(arr []int,k,l,h int) int {
	if l > h {
		return -1
	}

	m := (l + h) >> 1

	if k > arr[m] {
		return binarySearch(arr,k,m+1,h)
	} else if k < arr[m] {
		return binarySearch(arr,k,l,m-1)
	} else {
		return m
	}

}