20220622@二分查找算法

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，二分查找算法的前提是传入的序列是有序的（降序或升序），并且有一个目标值。

二分查找的核心思想是将 n 个元素分成大致相等的两部分，取中间值 a[n/2] 与 x 做比较，如果 x=a[n/2]，则找到 x，算法中止，如果 x<a[n/2]，则只要在数组 a 的左半部分继续搜索 x，如果 x>a[n/2]，则只要在数组 a 的右半部搜索 x。

二分查找虽然性能比较优秀，但应用场景也比较有限，底层必须依赖数组，并且还要求数据是有序的，对于较小规模的数据查找，我们直接使用顺序遍历就可以了，二分查找的优势并不明显，二分查找更适合处理静态数据，也就是没有频繁插入、删除操作的数据。
思路：
1) 先找到中间的下标 middle = (leftIndex + RightIndex) /2 ，然后用中间的下标值和需要查找的值（ FindVal）比较。

- 如果 arr[middle] > FindVal，那么就向 LeftIndex ~ (midlle-1) 区间找
- 如果 arr[middle] < FindVal，那么就向 middle+1 ~ RightIndex 区间找
- 如果 arr[middle] == FindVal，那么直接返回

2) 从第一步的 a、b、c 递归执行，直到找到位置。

3) 如果 LeftIndex > RightIndex，则表示找不到，退出。
代码/举例：
定义一个包含（1, 2, 5, 7, 15, 25, 30, 36, 39, 51, 67, 78, 80, 82, 85, 91, 92, 97）等值的数组，假设说要查找 30 这个值，如果按照循环的查找方法，找到 30 这个值要执行 7 次，那么如果是按照二分查找呢？二分查找的过程如下：
left = 1, right = 18; mid = (1+18)/2 = 9; 51 > 30
left = 1, right = mid - 1 = 8; mid = (1+8)/2 = 4; 15 < 30
left = mid + 1 = 5, right = 8; mid = (5+8)/2 = 6; 30 = 30 查找完毕

如上所示只需要执行 3 次，大大减少了执行时间，具体代码实现如下所示：
```go
// 二分查找法
// 二分查找算法的前提是传入的序列是有序的（降序或升序）
// 并且有一个目标值
package main

import "fmt"

var  n =  0
func BinaryFind(arr *[]int,left,right,val int)  {
	n++

//判断left是否大于right
	if left > right {
		fmt.Println("Not found!")
		return
	}

//先找到中间的下标
	mid := (left+right) / 2
	
	//按查找逻辑进行查找
	if (*arr)[mid] > val {
		// 要查找的值在mid的左侧。范围在left~mid+1
		BinaryFind(arr,left,mid+1,val)
	} else if (*arr)[mid] < val {
		BinaryFind(arr,mid+1,right,val)
	} else {
		fmt.Printf("第%v次查找\n",n)
		fmt.Println("Found: ",mid)
	}

}

func main()  {
	//定义一个数组
	arr := []int{1, 2, 5, 7, 15, 25, 30, 36, 39, 51, 67, 78, 80, 82, 85, 91, 92, 97}
	BinaryFind(&arr,0,len(arr)-1,2)
	fmt.Println("main arr=",arr)
}
```
执行结果
```
第4次查找
Found:  1
main arr= [1 2 5 7 15 25 30 36 39 51 67 78 80 82 85 91 92 97]
```