# 二分查找

	func binarySearch(list []int, target int) int {
	if len(list) == 0 {
	return -1
	}

	low, high := 0, len(list)-1
	for high >= low {
	mid := (high + low) / 2
	val := list[mid]
	if val == target {
	return mid
	} else if val > target {
	high = mid - 1
	} else if val < target {
	low = mid + 1
	}

	}
	return -1
	}

# 算法题

# 1. 山脉数组的峰顶索引

https://leetcode.cn/problems/peak-index-in-a-mountain-array/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/09_BinarySearch/level_2/topic_1.go

符合下列属性的数组 arr 称为 山脉数组 ：
arr.length >= 3
存在 i （ 0 < i < arr.length - 1 ）使得
arr[0] < arr[1] < ... arr[i-1] < arr[i]
arr[i] > arr[i+1] > ... > arr[arr.length - 1]
给你由整数组成的山脉数组 arr ，返回满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。
你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。

	func peakIndexInMountainArray(arr []int) int {
	low, high := 1, len(arr)-2

	for low <= high {
	mid := (low + high) / 2
	leftVal, midVal, righVal := arr[mid-1], arr[mid], arr[mid+1]
	if leftVal < midVal && righVal < midVal {
	return mid
	} else if leftVal < midVal && righVal > midVal {
	low = mid + 1
	} else if leftVal > midVal && righVal < midVal {
	high = mid - 1
	}
	}

	return 0
	}

# 2. 寻找旋转排序数组中的最小值

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/09_BinarySearch/level_2/topic_2.go

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

	func findMin(nums []int) int {
	low, high := 0, len(nums)-1

	for high > low {
	mid := (high + low) / 2
	if nums[mid] < nums[high] {
	high = mid
	} else {
	low = mid + 1
	}
	}
	return nums[low]
	}

# 3. 验证二叉搜索树

https://leetcode.cn/problems/validate-binary-search-tree/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/09_BinarySearch/level_2/topic_3.go

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

	func isValidBST(root *TreeNode) bool {
	if root == nil {
	return true
	}

	low, high := math.MinInt, math.MaxInt
	return subValidBST(root.Left, low, root.Val) && subValidBST(root.Right, root.Val, high)
	}

	func subValidBST(root *TreeNode, low, high int) bool {
	if root == nil {
	return true
	}

	if root.Val >= high \|\| root.Val <= low {
	return false
	}

	return subValidBST(root.Left, low, root.Val) && subValidBST(root.Right, root.Val, high)
	}

# 4. 将有序数组转换为二叉搜索树

https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/09_BinarySearch/level_3/topic_1.go

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

	func sortedArrayToBST(nums []int) *TreeNode {
	if len(nums) == 0 {
	return nil
	}

	mid := len(nums) / 2
	root := &TreeNode{nums[mid], nil, nil}
	root.Left = sortedArrayToBST(nums[:mid])
	root.Right = sortedArrayToBST(nums[mid+1:])

	return root
	}

数据结构算法