折半查找

元素查找介绍

查找也被称为检索，算法的主要目的是在某种数据结构中，找出满足给定条件的元素（以等值匹配为例）。如果找打满足条件的元素，则代表查找成功，否则查找失败。
在进行查找时，对于不同的数据结构以及元素集合状态，会有相对匹配的算法，在使用时也需要注意算法的前置条件。在元素查找相关文章中只讨论数据元素只有一个数据项的情况，即关键字（key）就是对应数据元素的值，对应到具体的数据结构，可以理解为一维数组。

• 顺序查找

也称为线性查找，是最简单的查找方法。思路也很简单，从数组的一边开始，逐个进行元素的比较，如果与给定的待查找元素相同，则查找成功，如果整个扫描结束后，仍未找到相匹配的元素，则查找失败。

• 折半查找

也称为二分查找，是一种效率相对较高的查找方法。使用该算法的前提要求是，元素已经有序，因为算法的核心思想是尽快的缩小搜索区间，这就需要保证在缩小范围的同时，不能有元素的遗漏。

• 索引查找

索引查找主要分为基本索引查找和分块查找，核心思想是对于无序的数据集合，先建立索引表，使得索引表有序或分块有序，结合顺序查找与索引查找的方法，完成查找。

折半查找

• 输入

n个数的有序序列，以数组为例，默认升序。
待查找元素key

• 输出

查找成功：返回元素所在位置编号
查找失败：返回-1或自定义失败标识

• 算法说明

算法的核心思想是：不断的缩小搜索范围，每次取区间的中心来进行比较，会有三种情况发生
1 与key相等：直接返回对应的位置
2 比key大：由于元素有序，要查找的元素一定在左侧（如有），于是搜索区间变为左一半
3 比key小：由于元素有序，要查找的元素一定在右侧（如有），于是搜索区间变为右一半

于是，只要不断重复取中间比较和指定新的搜索区间这两个步骤，直到区间的两个端点已经重合（代表搜索完毕）或者找到元素时为止。

• 算法流程

查找关键字为7的元素：

第1次比较：mid坐标为4，对应元素为10，大于7，则区间变为左一半：[0,3]
第2次比较：mid坐标为1，对应元素为1，小于7，则区间变为右一半：[2,3]
第3次比较：mid坐标为2，对应元素为7，等于7，返回逻辑序号：mid+1 = 3

伪代码

折半查找需要不断的改变区间和取中间元素进行判断，只要明确key与比较元素的关系就可以确定新的比较区间，然后循环整个过程。
伪代码表示如下：

left = 1
right = A.length
while left <= right
    mid = (left+right)/2
    if A[mid] == key
        return mid
    else if A[mid]>key
        right = mid - 1
    else
         left = mid - 1
return -1