6-10 二分查找

发表于 更新于 阅读次数： 本文字数： 448 阅读时长 ≈ 1 分钟

前言：
为了找工作，再次刷一下PTA上的数据结构习题，顺便在博客里简单记录一下题目里面的一些坑。

6-10 二分查找
https://pintia.cn/problem-sets/15/problems/923

经典的二分查找，做这道题的时间都用在了二分查找的几个细节上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Position BinarySearch(List L, ElementType X) {
	int begin= 0, end = L->Last;
	
	while (begin<=end)
	{
		int mid = (begin + end) / 2;

		if (L->Data[mid] == X)
		{
			return mid;
		}
		else if (L->Data[mid]>X)
		{
			end = mid - 1;
		}
		else // mid < X
		{
			begin = mid + 1;
		}
	}

	return NotFound;
}