折半查找

折半查找：又称二分查找，仅适用于有序的顺序表

算法思想：
1）首先将给定值key与表中中间位置元素的关键字比较
2）若相等，则返回该元素的位置；若不等，则在前半部分或者是后半部分进行查找
3）查找序列升序时，若key小于中间元素，则查找前半部分；若key大于中间元素，则查找后半部分
4）重复该过程，直到找到查找的元素为止，或查找失败

注意low<=high：

折半查找的判定树：

查找成功的平均比较次数：[log2(n+1)]-1，折半查找的时间复杂度为O(log2n)

顺序查找适用于顺序存储和链式存储，序列有序无序皆可；折半查找只适用于顺序存储，且要求序列一定有序