2021-02-02

二分查找（折半查找）

二分查找的过程和序列的下标从0开始还是从1开始无关。一般我们从1开始

数据结构重点讲过，这里不多将知识点了，直接上代码：

值得注意的是，如果二分上界超过int型数据范围的一半，那么当欲查询元素在序列较靠后的位置时，语句mid=（left+right）/2中的left+right就有可能超过int而导致溢出，此时一般使用mid=（left+right）/2=2left/2  -  left/2  +  right/2  =  left  +  （right  -  left）/2 这条等价语句作为代替以避免溢出。另外，二分法可以使用递归进行实现，但是在程序设计时更多采用的是非递归的写法。