目录

一.什么是二分查找法？

二.算法要求

三.算法思想

图解（要找的数k的值为3）

 参考代码

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序储存结构，而且表中元素按关键字有序排列。 

1.必须是有序排列。

例如数列   arr[]={1，2，3，4，5，6，7，8，9}          查找的数为k=3；

这里的left，right，mid记录的是数组下标

1.用left指向数列最左边的数（1），即left=0；

2.用right指向数列中最右边的数（9），即right=8；

3.用mid记录下标为（left+right）/2的数，即数组中间的数（5）；

这一步完成后，就是把arr[]数组分为了两个子数组，用arr[mid]隔开

即：      {1，2，3，4}           5         {6，7，8，9}

4.用arr[mid]与目标数k的大小进行比较，有三种情况

（1）arr[mid]=k;  即找到了

  (2)如果k比arr[mid]（即中间的那个数）大，则说明目标数（k）在右边的那个子数组中，所以就变成了在右边数组中找目标元素；方法和上面的类似，所以我们只需要将left指向改变为右边那个子数组的最左边的元素，即left=mid+1；

  (3)同理，如果k比arr[mid]小，则说明目标数（k）在左边的那个子数组中，所以就变成了在左边数组中找目标元素；我们只需要将right指向改变为左边那个子数组的最右边的元素，即right=mid-1；

5.只需要重复第四步的操作就可以把k的值的位置找到；

输出

！！！！