【排序算法go】二分查找1 递归实现 2 非递归实现

63 阅读 0 评论 42 点赞

我是靠谱客的博主慈祥飞机，这篇文章主要介绍【排序算法go】二分查找1 递归实现 2 非递归实现，现在分享给大家，希望可以做个参考。

1 递归实现

二分查找递归实现，关键是要确定终止条件

package search

//递归实现
func BinarySearch(arr []int,dst int) int{
	mid := len(arr)/2

	//递归最重要的是确定终止条件
	if len(arr) == 0{
		return -1
	}
	//查找成功
	if arr[mid]== dst{
		return mid
	}else if dst < arr[mid]{
		arr = arr[:mid - 1]
	}else {
		arr = arr[mid+1:]
	}
	//继续递归
	return BinarySearch(arr,dst)
}

2 非递归实现

//非递归实现
func BinarySearchEx(arr []int,dst int) int{

	for len(arr)!=0{
		mid := len(arr)/2
		if dst == arr[mid]{
			return mid
		}else if dst < arr[mid]{
			arr = arr[:mid-1]
		}else{
			arr = arr[mid+1:]
		}

	}
	return -1
}

可以看到代码比用C/C++写简洁很多