二分查找

前提：有序数组。

一、建立数组

二、传参

int a[] 数组

int left,int right 当前查找范围限定（left=0;right=n-1；10个数即n=10;left=0;right=9）

const int& x 待查找数值（假如查找27）

三、取中间值middle判断

如果27==7 返回当前middle值(0+9)/2=4

如果27 > 7查找右半段

if (x > a[middle]) return BinarySearch(a, middle+1, right,x); //设定右半段范围（right值不变middle+1）

如果27<7查找左半段

else return BinarySearch(a, left,middle-1, x); //设定左半段范围（left值不变middle-1）

当前查找右半段即 left=5; right=9

如果27==25 返回当前middle值(5+9)/2=7

……

如此继续递归调用BinarySearch函数

直到 middle= (8 + 9)/2 = 8时; 27==27; return middle

[特例]

如果要找元素在边上的话，如36，那么下一次就是left=9;right=9;自然middle也等于9。

[总结]

子问题：范围内取中值；递归不断缩小确定范围。

[代码]

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int search(int array[], int n, int v)
 5 {
 6     int left, right, middle;
 7     left = 0, right = n - 1;
 8 
 9     while (left <= right) 
10     {
11         middle = (left + right) / 2;
12         if (array[middle] > v) 
13             right = middle - 1;
14         else if (array[middle] < v) 
15             left = middle + 1;
16         else 
17             return middle;
18     }
19     return -1;
20 }
21 
22 
23 int main()
24 {
25     int array[10] = {1, 2, 3, 6, 7, 7, 8, 9, 13, 19};
26     cout << search(array, 10, 19) << endl;
27     return 0;
28 }

参考资料

1. 分块查找