100个python算法讲解：折半查找

1．问题描述
一组包含N个有序整数的序列已存储在一维数组中，要求采用二分查找法确定整数m在该数组中的具体位置。若成功找到，则输出对应的下标；若未找到，则显示“Not be found!”。

2．问题分析
二分查找法，又称为折半查找，其本质属于分治算法的一种形式。所谓分治算法，即通过将复杂的问题划分为多个较小的子问题，这些子问题彼此独立且与原问题具有相同的性质。通过对这些小规模问题的求解，最终实现对整体问题的解决。当每次将问题划分为两个部分进行处理时，这种方法被称为二分法。需要特别指出的是，该查找方法仅适用于已排序的数据序列。

二分查找的基本操作流程为：在每次查找之前首先明确待查数据的范围。设low和high两个指针（满足low < high）分别表示当前搜索区间的起始和结束位置，并令mid指针指向当前区间的中间位置，计算公式为mid = (low + high) / 2。随后将目标值m与mid所指向元素进行比较。如果m大于该元素，则调整搜索区间为mid之后的部分；反之，则调整为mid之前的部分。这一过程持续进行直至low > high时终止整个查找过程。

3．算法设计
由于N个有序数值已被存入数组中，根据数组下标的取值范围可知初始时low和high的取值应分别为0和N-1。除了三个用于控制搜索范围的指针变量low、high、mid之外，还需引入一个变量