下载文档原格式
二分法查找数值
二分法查找数值
二分法，也叫二分查找，是一种在有序数组中查找特定元素的算法。
其基本思想是每次取数组中间的值与目标值进行比较，然后根据比较结果舍弃一半的数据，直到找到目标值或者发现目标值不存在为止。
二分法查找数值的具体步骤如下：
1. 初始化左右指针，left=0，right=n-1。
（n为数组长度）
2. 当left小于等于right时，进行以下操作：
3. 取中间值middle=(left+right)/2。
4. 如果中间值等于目标值，返回目标值的位置。
5. 如果中间值大于目标值，说明目标值在middle的左侧，将right更新为middle-1。
6. 如果中间值小于目标值，说明目标值在middle的右侧，将left更
新为middle+1。
7. 如果循环结束还没有找到目标值，说明目标值不存在，返回-1。
二分法的时间复杂度为O(logN)，是一种十分高效的查找算法，因此
在很多情况下都被广泛应用。
其中包括在数据量较大的有序数组中查
找特定元素，以及在游戏中对答案进行猜测等。
总之，二分法通过逐步缩小查找范围，可以快速高效地查找指定元素，是一种很实用的算法。
在实际使用时，需要注意的是数组必须是有序的，否则无法保证算法正确性。
同时，由于函数栈空间有限，在数据
量较大时需要注意是否会爆栈。
⼆分查找详解看到⼀个⼤佬的博客，有⼀段内容让我深有感触：我周围的⼈⼏乎都认为⼆分查找很简单，但事实真的如此吗？⼆分查找真的很简单吗？并不简单。
看看 Knuth ⼤佬（发明 KMP 算法的那位）怎么说的：Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky...这句话可以这样理解：思路很简单，细节是魔⿁。
这两个⽉刷题遇到不少要⽤到⼆分查找的题。
当年学数据结构的时候觉得这是⼀个相当直观且好理解的算法，但是真正刷题时觉得这个算法需要注意的坑还是挺多的。
最普通的应⽤就是找某个元素的索引（数组有序且不重复），再复杂⼀些的还有找某个元素最左边或最右边的索引。
更⾼端的有对数组的索引或者数组中整数的取值范围进⾏⼆分查找，不过这⼀块还是万变不离其宗，查找的范围依旧是[left, right]，难点在于要怎么找到⼆分查找的对象。
⼆分查找基本框架def binarySearch(arr: List[int], target: int):n = len(arr)left, right = 0, ... # 左右边界的赋值可变while left ... right: # 需要注意有没有等号mid = left + (right - left) // 2if arr[mid] == target:... # 要不要直接returnelif arr[mid] < target:left = ... # 要不要加⼀elif arr[mid] > target:right = ... # 要不要减⼀return ... # 有返回mid的，有left的各种上⾯⼀段代码中的...部分是需要根据题⽬需要修改的地⽅，也就是⼆分查找的细节所在。
另外，计算mid的公式也可以写成mid = (left + right) // 2，按上⾯那样写是为了防⽌溢出（虽然在Python⾥并不会有整型溢出的问题，不过最好养成这个习惯）。
算法图解（⼆分查找）⼆分查找假设你要查找电话本⾥k开头的⼈⾥可能会直接滑动到中间因为你知道k在中间位置因为电话本是abcdef排序的嘛定义：⼆分查找就指从中间开始查找的逻辑做法注：# ⼆分查找必须是有序序列返回其位置# ⽆序⽆法进⾏⼆分查找返回null例如：⼆分查找： 利⽤⼆分查找每次取中间数有⼩数可以向上或向下取整数 100以内的数字最多7次可以找出来普通查找： ⽽普通查找则是从头到位遍历最好的情况是1 ⼀次找出最差是100次⼆分查找随着元素的增加并不会改变太⼤普通查找则会随元素的增加⽽增加⽐如说⼀个字典内有240000个单词普通查找最差情况：240000次出结果⼆分查找最差情况：17次出结果这就很明显的突出了⼆分算法的优势####这⾥我⽤（）括号⾥的数字代表log的下标⽤⼆分查找最多需要log（2）n步其实就是利⽤对数运算：对数运算：定义：幂运算的逆运算例如：10**2 = 100 log（10）100 = 210**3 = 1000 log（10）1000=32**5 = 32 log（2）32 = 5如果有8个元素你最多需要查找3次因为long8 = 3（2**3=8）1024个元素最多需要检查10个元素因为 1024 = 10（2**10=1024）def binary(lst, item):low = 0high = len(lst) - 1while low <= high:mid = round((low + high) / 2)guess = lst[mid]if guess == item: # 猜对了return midif guess > item:high = mid - 1 # 猜⼤了else:low = mid + 1 # 猜⼩了return Nonemy_list = [1, 3, 5, 7, 9]print(binary(my_list, 3)) # 1 返回的元素下标索引是0开始的print(binary(my_list, -1)) # None 因为不存在-1元素运⾏时间： 线性时间（linear time） 100个数字最多猜100次 40亿猜40亿次最多猜的次数等于列表的长度 对数时间（或log时间） 100个数字最多猜7次 40亿猜32次⼤O表⽰法： 简单查找每个元素需要n次运⾏时间为O（n） ⼆分查找运⾏时间为O（log（n））⼤O表⽰法计算的是操作数 O（log n）对数时间包括⼆分查找 O（n）线性时间 O（n * log n）快速排序算法 O（n**2）速度较慢排序法算法 O（n！）⾮常慢的算法⼩结： ⼆分查找⽐简单查找快的多 O（log n）⽐O（n）快，需要搜索的元素越多，前者⽐后者就快的越多 算法运⾏时间并不以秒为单位 算法运⾏时间是从其增速的⾓度度量的 算法的运⾏时间⽤⼤O表⽰法表⽰。
二分法查找
二分查找也称折半查找（Binary Search），是一种在有序数组中查找目标值的算法。
它的基本思想是将数组分为两部分，然后判断目标值可能存在的那一部分，并继续在该部分中进行查找，以此逐渐缩小查找范围，直到找到目标值或确定不存在。
二分查找的基本实现步骤如下：
1. 确定数组的左边界和右边界，初始时左边界为0，右边界为数组长度减1。
2. 计算数组的中间位置mid，可以使用公式mid = (left + right) / 2。
3. 比较中间位置的元素与目标值的大小关系：
- 如果中间位置的元素等于目标值，则找到目标值，返回中间位置。
- 如果中间位置的元素大于目标值，则目标值可能在左侧部分，更新右边界为mid - 1。
- 如果中间位置的元素小于目标值，则目标值可能在右侧部分，更新左边界为mid + 1。
二分查找虽然思路简单，但在实现过程中需要注意细节，如循环中的不等号是否应该带等号，mid是否应该加一等。
分析这些细节的差异以及出现这些差异的原因，有助于更加灵活准确地实现二分查找算法。
⼆分法查找（C语⾔）⼆分法是⼀种⾼效的查找⽅法，其适⽤于已经排好序的数组基本思路从数组最中间的数开始查找判断，若不是需要查找的数字，则⽐较⼤⼩，之后则在从中间分开的两边中的⼀边从最中间开始查找判断，以此类推算法描述这⾥以升序数组为例，降序数组类似1. 记录数组最中间数的下标，将其中的数与要查找的数进⾏⽐较2. 若相等，停⽌查找，若⼤于要查找的数，则将数组下标上限换为较⼤半区的最⼩下标；若⼩于要查找的数，则将数组下标的下限换为较⼩半区的最⼤下标3. 重复第⼀步，直到数组下标不能调换，若查找到则停⽌查找，若未找到，则返回不存在的结果代码实现这⾥以升序数组为例，降序数组类似# include<stdio.h>int f(int, int [], int);int main(){int n;int arr[10]={1,2,3,4,5,6,7,8,9,10};scanf("%d", &n);//输⼊要查找的数int m=f(n, arr, 10-1);if(f(n, arr, 10-1)!=-1)printf("该数所在下标为：%d\n", m);elseprintf("该数不存在\n");}int f(int n, int a[], int h){int i, l, mid;l = 0;while(l<=h)//注意有等号,因为可能最后⼀次查找就只剩⼀个数,则这时上下限下标相等{mid=(l+h)/2;//计算中间下标if(a[mid]==n)//判断是否为⽬标数return mid;else if(a[mid]<n)l=mid+1;//如果中间数⼩于⽬标数,则将数组下限改为较⼤半区的下限elseh=mid-1;//如果中间数⼤于⽬标数,则将数组上限改为较⼩半区的上限}return -1;//返回-1表⽰⽬标数不存在}。
二分法查找算法二分法查找算法，又称折半查找，是一种基于有序数组的查找算法。
它采用了逐步缩小查找范围的方法，能高效地找出目标数字在数组中的位置。
下面我们就来具体了解一下二分法查找算法的步骤。
第一步，确定查找范围。
由于二分法查找算法只适用于有序数组，所以我们需要先对数组进行排序。
然后，我们需要确定查找的范围，也就是最大值和最小值。
一般来说，最大值为数组末尾的值，最小值为数组开头的值。
第二步，找到中间值。
我们需要计算出最大值和最小值的平均值，来确定中间值。
由于数组是有序的，所以我们可以使用简单的方法计算中间值：中间值 = （最大值 + 最小值）/ 2。
如果中间值与目标数字相等，那么我们就找到了目标数字的位置；如果中间值比目标数字大，那么目标数字应该在左边，我们将右边的范围缩小到中间值左边的数字；如果中间值比目标数字小，目标数字应该在右边，我们将左边的范围缩小到中间值右边的数字。
第三步，重复查找过程。
我们继续按照上面的方法缩小查找范围，并不断计算中间值，直到找到目标数字的位置或者确定目标数字不存在于数组中为止。
如果查找范围被缩小到了最小值等于最大值的时候，且这个值不等于目标数字，说明目标数字不存在于数组中。
二分法查找算法的时间复杂度为O(log n)，是一种快速的查找算法。
但是它也有一些局限性，只适用于有序数组，不适用于链表等其他数据结构。
在有序数组中，如果需要频繁进行插入和删除操作，排序的时间复杂度会很高，影响算法效率。
以上就是二分法查找算法的基本步骤及其局限性。
在实际开发中，我们需要根据具体情况来选择使用哪种查找算法，在考虑算法效率的同时，也要考虑其他因素，比如数据结构的特点、操作的频率等等，才能选出最适合的算法。
二分法查找
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。
但是，二分查找要求线性表必须采用顺序存储结构，不宜用于链式结构，而且表中元素按关键字有序排列（解释：所以二分查找的时候一定要是有序的数组）
（1）将数据有序排列：先将一个数据集进行有序排列（可根据某种数值的大小降序或升序<当然排序的规则可根据业务规则自定义>，前提是需要查找的数据具备该规则同样的属性）；
（2）数据分半：就是将排序好的数据集切分成大致相等的两份数据集；
（3）查找数据：查找的时候直接和拆分数据集中的第一个或最后一个元素进行大小比较，不满足则表示数据不存在于该数据集中，满足则说明要查找的元素存在于当前数据集中。
1。
算法-⼆分法查找什么是⼆分法查找⼆分法查找主要是为了快速查找给定数组内，期待值在数组中的位置（下标）⼆分法查找通过对整个数组取中间值，判断期待值所在的范围并缩⼩范围，每次查找范围折半，直到范围的边界重合，得出期待值的位置，如果找不到返回null⼆分法有⼀个先决条件是：数组内元素必须是有序的简单图解给定⼀个包含1，3，5，7，8，9这⼀个元素的有序数组，求得期待值7所在的位置，下边⽤绿块表⽰指针所在位置若是按照直接遍历的⽅式，绿块会从数组的第⼀个下标开始⽐较，直到7所在的下标得到结果，遍历需要4次，下边演⽰下⼆分法的图⽰第⼀次，取值范围为整个数组，取数组长度中间值(0+5)/2取整2作为下标取中间值初始以数组的第⼀个下标与最后⼀个下标相加取中间值，如果不为整，舍去⼩数部分⽐较期待值与下标为2的值⼤⼩，发现5<7，7这个值应在中间值的右侧缩⼩查找范围为中间值+1与最⼤下标第⼆次，范围缩⼩为原数组的⼀半，下标不变，取中间值(3+5)/2=4下标4对应的值8，⼤于7，所以向左取范围最⼩下标3，最⼤下标4-1=3第三次，取中间值(3+3)/2=3，下标3上的值恰好与期待值相等，返回下标3虽然看起来只少了⼀次，原因在数组的长度⼩，另外就是期待值设置的⼩，再举个长⼀点的例⼦，这⾥有1-100的数组，100个元素，期待值为100简单遍历次数最⼤为元素的个数n次，本例中100次使⽤⼆分查找只需要log2n次，本例中7次！⼆分法查找的Java实现package binarysearch;/*** ⼆分查找：求得期待值在有序数组中的位置* @author hellxz*/public class MyBinarySearch {/*** ⼆分查找算法实现* @param orderedArray 有序数组* @param expect 期待数值* @return 期待值在数组中的下标，如果期待数值不在数组中，返回null*/public static Integer binarySearch(int[] orderedArray, int expect) {//low与high构成动态的数组下标范围//初始low下标为0，high为数组长度-1int low = 0;int high = orderedArray.length - 1;//当数组范围存在时，有两种情况：最⼩边界值⼩于最⼤边界值或两个边界值相等；//最⼩边界值不⼤于最⼤边界值是有意义的，表⽰范围的存在，如果范围不存在了，说明数组中⽆此元素while (low <= high) {//取两个边界下标的中间下标与中间值，作为下标时会⾃动取整int middle = (low + high) / 2;int middleVal = orderedArray[middle];//中间值与期待值相等，说明中间值的下标就是我们要找的期待数的下标if (middleVal == expect) {return middle;}//中间值⼩于期待值，我们需要将最⼩边界下标移到中间下标的下⼀位//此时，最⼤边界不变，最⼩边界变⼤，范围缩⼩原来⼀半if (middleVal < expect) {low = middle + 1;}//中间值⼤于期待值，说明最⼤边界应⼩于中间下标if (middleVal > expect) {high = middle - 1;}}//循环结束未返回下标说明数组中不存在期待元素，返回nullreturn null;}public static void main(String[] args) {int[] arr = { 2, 4, 5, 6, 10, 18, 19,22, 25, 70};int expectVal = 25;System.out.printf("当前期待的值为%d，其所在的下标为%d", expectVal, binarySearch(arr, expectVal));}}最后本⼈不是科班出⾝，很多知识都在学习中，算法与数据结构系列将不定时更新（学会哪个更哪个 ）。
数组二分法查找-概述说明以及解释1.引言1.1 概述在计算机科学中，数组是一种常见的数据结构，可以用于存储一系列相同类型的元素。
而二分法查找是一种高效的查找算法，它适用于有序数组中进行查找特定元素的情况。
数组的二分法查找是通过将数组分为两部分，并与目标元素进行比较来确定目标元素的位置。
具体步骤是首先确定数组的中间元素，然后将目标元素与中间元素进行比较。
如果两者相等，则目标元素找到；如果目标元素小于中间元素，则在前半部分继续查找；如果目标元素大于中间元素，则在后半部分继续查找。
通过重复这一过程，最终可以确定目标元素是否存在于数组中。
二分法查找具有时间复杂度为O(log n)的优势，相比于线性查找的时间复杂度O(n)，在处理大型有序数组时具有明显的效率提升。
因此，二分法查找在处理大规模数据集、需要频繁查找的场景中被广泛应用。
本文将介绍数组的二分法查找原理，深入阐述其优势，并探讨二分法查找在实际应用中的场景。
通过全面了解和掌握这一查找算法，可以使读者在实际问题中更加高效地进行查找操作。
1.2文章结构文章结构部分的内容可以包括以下内容：文章结构部分的主要目的是帮助读者了解整篇文章的组织和内容安排。
通过清晰的文章结构，读者可以更好地理解和掌握数组二分法查找的相关知识。
本文采用如下结构：1. 引言1.1 概述引言部分将介绍本文要讨论的主题——数组二分法查找的基本概念和原理。
通过引入问题的背景和重要性，读者可以更好地理解为什么需要数组二分法查找以及它的应用场景。
1.2 文章结构文章结构部分（即本节）将详细介绍本文的整体组织安排。
通过明确列出本文的各个部分和各部分的主要内容，读者可以清楚地了解到本文将要涵盖哪些内容和每部分的重点。
1.3 目的目的部分将概述本文的目标和意义。
通过明确说明本文的目的，读者可以更好地理解文章的价值和阅读的收获。
2. 正文正文部分将详细介绍数组二分法查找的基本概念、原理和算法。
本节将首先介绍数组的二分法查找的定义和基本思想，接着会详细解释二分法查找的原理及其实现方法。
二分法查找算法思路二分法查找算法，又称折半查找算法，是一种高效的查找算法。
它的思路是将待查找的元素与数组的中间元素进行比较，如果中间元素等于待查找元素，则找到了；如果中间元素大于待查找元素，则在左半部分继续查找；如果中间元素小于待查找元素，则在右半部分继续查找。
通过不断地将查找范围缩小一半，最终找到待查找元素或确定元素不存在于数组中。
二分法查找算法的基本步骤如下：1. 将数组按照升序排列，确保待查找的数组是有序的。
2. 初始化左边界left为0，右边界right为数组的长度减1。
3. 当left小于等于right时，执行以下步骤：1) 计算中间位置mid，mid = (left + right) / 2。
2) 如果中间元素等于待查找元素，返回mid。
3) 如果中间元素大于待查找元素，更新right为mid-1。
4) 如果中间元素小于待查找元素，更新left为mid+1。
4. 如果找不到待查找元素，返回-1表示查找失败。
二分法查找算法的时间复杂度为O(logN)，其中N为数组的长度。
这是因为每次查找都将查找范围缩小一半，最坏情况下需要执行logN次查找操作。
下面通过一个例子来说明二分法查找算法的应用过程。
假设有一个有序数组arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]，我们要查找元素11。
根据算法步骤，初始化left为0，right为数组长度减1，即left = 0，right = 9。
第一次查找，计算中间位置mid = (left + right) / 2 = (0 + 9) / 2 = 4。
中间元素arr[4] = 9小于待查找元素11，更新left为mid+1，即left = 5。
第二次查找，计算中间位置mid = (left + right) / 2 = (5 + 9) / 2 = 7。
中间元素arr[7] = 15大于待查找元素11，更新right 为mid-1，即right = 6。
二分法查找元素公式(二)二分法查找元素公式1. 什么是二分法查找？二分法是一种基于比较的查找算法，也称为折半查找。
它是针对已排好序的数组进行查找的一种高效算法。
2. 二分法查找的原理二分法查找的原理是通过将要查找的范围分成两半，每次取中间位置的元素与目标值进行比较，根据比较的结果来确定下一次查找的范围，从而将查找范围逐渐缩小，直到找到目标值或者确定目标值不存在。
3. 二分法查找的公式二分法查找的公式如下：mid = (low + high) / 2其中，low表示当前查找范围的最小索引，high表示当前查找范围的最大索引，mid表示当前查找范围的中间索引。
4. 二分法查找的步骤二分法查找的步骤如下：•初始化low和high分别为数组的第一个索引和最后一个索引；•循环直到low大于high：–计算mid的值；–如果mid对应的元素等于目标值，则返回mid；–如果mid对应的元素小于目标值，则更新low为mid+1；–如果mid对应的元素大于目标值，则更新high为mid-1；•返回 -1，表示目标值不存在于数组中。
5. 举例说明假设有以下有序数组[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]，我们要查找数字9。
•初始时，low为0，high为9；•第一次循环，计算mid = (0 + 9) / 2 = 4，数组中索引为4的元素为9，找到目标值；•返回4。
通过二分法查找，我们可以快速定位到目标值9的位置。
6. 总结二分法查找是一种高效的查找算法，它的公式为mid = (low + high) / 2。
通过将查找范围逐渐缩小，可以快速找到目标值。
在处理大规模的有序数组查找时，二分法查找是一种常用的方法。
⼆分查找（BinarySearch）1、定义⼆分查找⼜称折半查找，它是⼀种效率较⾼的查找⽅法。
⼆分查找要求：线性表是有序表，即表中结点按关键字有序，并且要⽤向量作为表的存储结构。
不妨设有序表是递增有序的。
2、基本思想⼆分查找的基本思想是：设R[low..high]是当前的查找区间（1）⾸先确定该区间的中点位置：（2）然后将待查的K值与R[mid].key⽐较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续⼆分查找，具体⽅法如下：①若R[mid].key>K，则由表的有序性可知R[mid..n].keys均⼤于K，因此若表中存在关键字等于K的结点，则该结点必定是在位置mid左边的⼦表R[1..mid-1]中，故新的查找区间是左⼦表R[1..mid-1]。
②若R[mid].key<K，则要查找的K必在mid的右⼦表R[mid+1..n]中，即新的查找区间是右⼦表R[mid+1..n]。
下⼀次查找是针对新的查找区间进⾏的。
因此，从初始的查找区间R[1..n]开始，每经过⼀次与当前查找区间的中点位置上的结点关键字的⽐较，就可确定查找是否成功，不成功则当前的查找区间就缩⼩⼀半。
这⼀过程重复直⾄找到关键字为K的结点，或者直⾄当前的查找区间为空(即查找失败)时为⽌。
3、存储结构⼆分查找只适⽤顺序存储结构。
4、⼆分查找算法/*折半查找*/int Binary_Search(int a*,int n,int key){int low,high,mid;low=1; /*定义最底下标为记录⾸位*/high=n; /*定义最⾼下标为记录末位*/while(low<=high){mid=(low+high)/2; /*折半*/if(key<a[mid])high=mid-1;if(key>a[mid])low=mid+1;elsereturn mid;}return 0;}也可以如下构造参数：int BinSearch(SeqList R，KeyType K){//在有序表R[1..n]中进⾏⼆分查找，成功时返回结点的位置，失败时返回零int low=1;int high=n;int mid;//置当前查找区间上、下界的初值while(low<=high)//当前查找区间R[low..high]⾮空{mid=(low+high)/2；if(R[mid].key==K)return mid；//查找成功返回if(R[mid].kdy>K)high=mid-1;//继续在R[low..mid-1]中查找elselow=mid+1；//继续在R[mid+1..high]中查找}return 0;//当low>high时表⽰查找区间为空，查找失败}5、算法分析①执⾏过程设算法的输⼊实例中有序的关键字序列为(05，13，19，21，37，56，64，75，80，88，92)拓展：⼆分查找判定树⼆分查找过程可⽤⼆叉树来描述：把当前查找区间的中间位置上的结点作为根，左⼦表和右⼦表中的结点分别作为根的左⼦树和右⼦树。
二分查找算法二分查找算法是一种常见的查找方法，在计算机科学领域被广泛应用。
它的基本思想是通过将有序数组中间的元素与查找目标进行比较，缩小查找范围，最终定位目标元素的位置。
本文将深入探讨二分查找算法的实现原理、应用场景以及优化方法。
一、二分查找算法的基本原理二分查找又称折半查找，基本思想是在有序数组中查找特定元素。
它的实现原理是利用“分治思想”，将查找问题逐步缩小。
具体地，假设要查找的数组为a，查找范围为[left, right]，目标元素是key，则二分查找的基本算法流程如下：1.计算数组中心元素下标mid，mid=(left+right)/2；2.将目标元素key与中心元素a[mid]进行比较，若相等，则返回mid；3.若key>a[mid]，则在右半部分继续查找，即[left, right]变为[mid+1, right]；4.若key<a[mid]，则在左半部分继续查找，即[left, right]变为[left, mid-1]；5.重复以上步骤，直到找到目标元素或者[left, right]变为空。
下面给出一个二分查找的示例代码：```int binarySearch(int a[], int left, int right, int key) { while (left <= right) {int mid = (left + right) / 2;if (a[mid] == key)return mid;else if (a[mid] < key)left = mid + 1;elseright = mid - 1;}return -1; //未找到}```二、二分查找算法的应用场景二分查找算法的时间复杂度为O(logn)，即查找的时间随着数组元素个数的增加而增加的速度很慢，因此它适用于处理大量数据的情况，比如在搜索引擎中对关键词进行搜索；在数字密码破解中，通过二分查找可以快速猜测密码；在哈希表中，二分查找可用于快速定位元素位置等。
二分查找法过程详解
二分查找法，也称为二分搜索法或折半查找法，是一种常用的查找算法。
该算法的特点是每次查找都将查找区间缩小一半。
二分查找法适用于有序数组或有序列表。
下面详细介绍二分查找法的过程：
1. 首先，确定查找的区间。
假设有序数组为a，查找范围是[l, r]，则初始时l=0，r=n-1，其中n为数组a的长度。
2. 计算中间位置mid=(l+r)/2。
3. 判断中间位置对应的数值与目标值的大小关系。
如果中间位置对应的数值大于目标值，则在左边子数组中继续查找，更新查找范围为[l, mid-1]；如果中间位置的数值小于目标值，则在右边子数组中继续查找，更新查找范围为[mid+1, r]。
4. 重复执行步骤2和步骤3，直到找到目标值或者查找范围缩小为0。
5. 如果查找成功，则返回目标值在数组中的下标；否则，返回-1表示没有找到目标值。
二分查找法的时间复杂度为O(log n)，其中n为数组的长度。
该算法在查找静态数据集合中的数据非常有效，但是在数据集合需要频繁地进行插入或删除操作时，则需要重新排序，效率较低。
- 1 -。
六、二分法查找（Binary Search）
如何从数组里找一个元素的位置？如果排列是无序的，我们只能从头到尾找，但如果排列是有序的，我们则可以用别的更好的方法，二分查找法就类似我们在英汉词典里找一个单词的方法。
如下图所示（假如我们要查找的数字是“88”）：
下面我给出了一段demo代码，来演示二分查找法比顺序查找快多少，代码为了方便起见，初始化有序表的时候填入的数字都是均匀的，而事实上数字可以不均匀。
你可以调整一下代码中TABLE_SIZE的值，从500，调到5000，再调到10000，再调到30000……你会发觉两者差距越来越明显。
我在第一篇的地方提到二分查找法的复杂度为Ο(logn)，而顺序查找的复杂度
为Ο(n)，当n越来越大时候，Ο(logn)的优势也就越来越明显，当然了，前提是“有序”，才可用二分查找法。
#include "stdio.h"
#include "time.h"
#define TABLE_SIZE 50000
//returns the position, -1 means failed.
int SequenceSearch(int *pArray, int iArraySize, int iVal)
{
int i;
for(i=0; i<iArraySize; i++)
{
if(pArray[i]==iVal)
return i;
}
return -1;
}
//returns the position, -1 means failed.
int BinarySearch(int *pArray, int iArraySize, int iVal)
{
int iLeft = 0;
int iRight = iArraySize-1;
while(iLeft<=iRight)
{
int iMiddle = (iLeft+iRight)/2;
if(iVal < pArray[iMiddle])
{
iRight = iMiddle-1;
}
else if(iVal > pArray[iMiddle])
{
iLeft = iMiddle+1;
}
else
return iMiddle;
}
return -1;
}
int main(int argc, char* argv[])
{
//make the table
int table[TABLE_SIZE];
int i;
for(i=0; i<TABLE_SIZE; i++)
{
table[i] = i*2;
}
clock_t ctBegin = clock();
//Test sequence search
for(i=0; i<TABLE_SIZE; i++)
{
SequenceSearch(table, TABLE_SIZE, i*2);
}
clock_t ctEnd = clock();
printf("SequenceSearch takes %d clocks.\n", ctEnd-ctBegin);
//Test binary search
ctBegin = clock();
for(i=0; i<TABLE_SIZE; i++)
{
BinarySearch(table, TABLE_SIZE, i*2);
}
ctEnd = clock();
printf("BinarySearch takes %d clocks.\n", ctEnd-ctBegin);
return 0;
}
这篇文章是不是太简单了点？OK，下一篇技术含量要高一点了。
