算法 - 二分查找

什么是二分查找

二分查找算法，也称折半搜索算法对数搜索算法，是针对的是一个有序的数据集合中搜索的算法。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。 譬如我随机有序的写下0-9 十个数字，没猜一次我都会告诉你数值是大了还是小了，这样你就可以有效的缩小差早范围。

实现

func Search(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := (right + left) / 2
		num := nums[mid]
		if num == target {
			return mid
		} else if num > target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return -1
}

因为是范围查找，所以需要通过两个变量 left, right 表示当前查找的区间范围。第一次的查找范围就是整个数组的长度，mid 代表查找范围的中间位置。通过对比 num 与 target 的大小，来更新接下来要查找的区间范围，直到找到或者区间缩小为 0，就退出。

如果数据的长度为偶数，那么在倒数第二次查找的时候 left 就会等于 right，所以循环的条件必须是left <= right，就算只剩下最后一个元素也需要做对比。

(right + left) / 2 在计算中间位置的时候，如果数组长度很长。left 到了 right，那么在计算的时候可能导致溢出。 改进写法， low + (right - left) / 2 先计算后面的除法，可以防止溢出。

二分查找最基础的实现很简单，难的是各种变种写法。

二分查找不重复数组有序数组里面是否存在某个值。并返回最后出现的位置。

static int Bsearch(int[] a, int val)
{
    var low = 0; 
    var high = a.Length - 1; 
    var mid = 0;
    while (low <= high)
    {
        // 计算中间位置
        mid = low + (high - low) / 2;
        var temp = a[mid];
        if (temp == val)
        {
            // 如果mid 是最后一个位置说明就是就最后一次出现的位置。如果mid+1不等于val 也表示是最后一次出现的位置
            if (mid == len || a[mid + 1] != val)
                return mid;
            else
                low = mid + 1;
        }
        else if (temp < val)
            low = mid + 1;
        else if (temp > val)
            high = mid - 1;
    }

    return mid;
}

二分查找局限性和使用场景

1. 二分查找只能用在数据是通过顺序表来存储的数据结构上。如果的数据是通过其他数据结构存储的，则无法应用二分查找。
2. 二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中。针对动态变化的数据集合，二分查找将不再适用。
3. 如果要处理的数据量很小，完全没有必要用二分查找，顺序遍历就足够了，只有数据量比较大的时候，二分查找的优势才会比较明显。
4. 如果数据之间的比较操作非常耗时，不管数据量大小，都推荐使用二分查找
5. 二分查找的底层需要依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻。