说说二分查找

type

status

date

slug

summary

二分查找

【引子】给定【已排好序的】n个元素，现要在n个元素中找到某个值x。

一般直接循环遍历所有值，依次匹配即可，但利用二分查找更快。

标准解释

二分查找的思想：

将n个元素分成个数大致相同的两半，用a[n/2]与目标值x比较。也就是用n个数的中间值为基准，如果x = [a/2]，则找到x,算法终止。如果x < a[n/2]，则只要在数组a的左半部分继续搜索x。如果x > a[n/2]，则只要在数组a的右半部分继续搜索x。

俺的理解

假定n个元素由小到大排好序~，现在要找其中的某个值x。二分查找就是要咱用这n个数的中间值来一步步向目标值x逼近（下面统称目标值为x，中间值为m）。怎么做到逼近呢？二分查找利用元素已排好序的这个特性，如果发现x比m小，就往m的左边查找。如果发现x比m大，就往m的右边寻找。

咱假设x比m小来说事。嘿嘿，那咱就可以确定x是在m的左边！那么下一次查找就从m左边的数字中找，因为m右边的数肯定比x大呀，所以咱就能缩小查找范围，m以右的数字、包括m咱也不要了。下一次逼近到更小的范围，用更小范围的中间值，同时也是更加接近m的值来与x比较是否相等，若相等，就找到x。重复上面的动作！最后查找范围逼近到最小，咱就找到了x：

一路上，由于m知道x比自己大还是小这个重要提示，经过对x的一步步的左右逼进，x所在的范围慢慢缩小，m终于找到了x。

二分查找也很像是猜数字游戏，1~100，咱每次都猜中间值，而裁判会告诉我们猜大了还是猜小了~

具体算法(Golang)

从1到n的字符串拼接，求字符串长度？

不是二分查找，是今儿算法课上的一道题，作为分治策略的引子