0%

二分查找

发表于 更新于 分类于 ，

  • 查找对象：顺序存储的有序表。

  • 思路：由于查找的表是有序的（假设是从小到大），地址在中间位置的元素必然在排序中也属于中间次序。

    step1：设置两个指针，一个（low）指向第一个元素，另一个（high）指向最后一个元素。

    step2：找到中间元素（mid=(low+high)/2）与要查找的元素比较。

    step3：若相等，万事大吉，返回当前位置（mid）；

    ​ 若该元素大于目标元素，说明目标元素在左侧，指针high=mid-1，查找左边；

    ​ 若该元素小于目标元素，说明目标元素在右侧，指针low=mid+1，查找右侧。

    step4：重复step2、step3，指针查找到目标元素。

  • 代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/** 二分查找 
* @Date:2019/03/14
* @Author:Jason Hu
*/
#include<iostream>
using namespace std;

int binary_search(int table[], int key)
{
	int low = 0;
	int high = 9;
//	特别注意：这里必须是 <= 
	while(low<=high)
	{
		int mid = (low+high)/2;
		if(key==table[mid]) return mid;
		if(key>table[mid]) low = mid+1;
		if(key<table[mid]) high = mid-1;
	}
}

int main()
{
//	顺序存储的有序表
	int table[10] = {5, 13, 19, 21, 37, 56, 64, 75, 80, 92};
//	查找对象
	int key = 64;
	cout<<binary_search(table,key)<<endl;
	return 0;
}