二分查找算法分析与总结

川长思鸟来 2023-07-13 10:46 40阅读 0赞

# 原理 #

你就想着你在做猜数字游戏，1-100之间，你需要猜对那个数，你会先取50问他对不对，如果对了那就是50游戏结束；如果猜的大了，那你肯定不会在50-100之间去猜了，而是收缩区间在1-49之间**(均为闭区间)**继续猜，你会继续取中间值问他对不对，根据大小做出区间的控制，以此类推逐渐收缩就能知道那个数字具体是多少。什么时候返回结果？即你找到了这个数，或者区间收缩为0了不能再收缩了（找完了但是没找到）。

当然不用二分的话，最笨的办法就是你一个一个问他对不对，从1问到100，最差的情况就需要猜100次...反映到代码就是顺序遍历。

条件：有序的数据集合

二分实现（需要注意的地方都在注释中）

func search2(arr []int, low, high, num int) int {
    
    	// 缩小区间最后会出现[12,12]的情况，因此循环的条件不能是low < high，而是low <= high，
    	// 当然如果你开始传入的high本身就是len(arr)而非len(arr)-1，那此处就可以low < high
    	for low <= high {
    		midIndex := (low + high) / 2
    		//fmt.Println("low=", low, "   high=", high, "   mid=", midIndex)
    		if arr[midIndex] == num { // 如果最中间的值就是要找的数，直接返回索引
    			return midIndex
    		} else if num < arr[midIndex] {
    			high = midIndex - 1
    		} else if num > arr[midIndex] { 
    			low = midIndex + 1 // 移动区间端点进行缩小区间
    		}
    	}
    
    	return -1
    }

可以看到，每次执行的部分都是一样的逻辑，还可以用递归实现：

func search3(arr []int, low, high, num int) int {
    	if low > high { // 没找到时递归结束
    		return -1
    	}
    
    	midIndex := (low + high) / 2
    	if arr[midIndex] == num {
    		return midIndex
    	} else if num < arr[midIndex] {
    		high = midIndex - 1
    	} else if num > arr[midIndex] {
    		low = midIndex + 1
    	}
    
    	return search3(arr, low, high, num)
    }

先写这么多，完了继续补充~