二分查找_详解[原理+题目]

6-1 二分查找（20 point(s))

本题要求实现二分查找算法。
函数接口定义：
Position BinarySearch( List L, ElementType X );

其中List结构定义如下：
typedef int Position;
typedef struct LNode List;
struct LNode {
ElementType Data[MAXSIZE];
Position Last; / 保存线性表中最后一个元素的位置 */
};

L是用户传入的一个线性表，其中ElementType元素可以通过>、==、<进行比较，并且题目保证传入的数据是递增有序的。函数BinarySearch要查找X在Data中的位置，即数组下标（注意：元素从下标1开始存储）。找到则返回下标，否则返回一个特殊的失败标记NotFound。
裁判测试程序样例：
#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10
#define NotFound 0
typedef int ElementType;

typedef int Position;
typedef struct LNode List;
struct LNode {
ElementType Data[MAXSIZE];
Position Last; / 保存线性表中最后一个元素的位置 */
};

List ReadInput(); /* 裁判实现，细节不表。元素从下标1开始存储 */
Position BinarySearch( List L, ElementType X );

int main()
{
List L;
ElementType X;
Position P;

L = ReadInput();
scanf("%d", &X);
P = BinarySearch( L, X );
printf("%d\n", P);

return 0;

}

/* 你的代码将被嵌在这里 */

输入样例1：
5
12 31 55 89 101
31

输出样例1：
2

输入样例2：
3
26 78 233
31
输出样例2：
0

当给一个顺序表,与另一个元素的值,要求查找该值是否出现在指定的顺序表中,我们可以采用遍历查找的方式,但若对于一个元素的值呈单调递增且单调递减的顺序表,我们有一种更快的方式----二分查找.

二分查找与数学中的二分法估计零点的值原理是类似的,都是不断将原区间折半排除,最终得到更为精确的范围或值.

我们先采用一个例子,现在给一个10个元素的顺序表,分别从1-10;要求查找元素为8;因为元素是单调递增的,我们采用二分查找.二分查找有三个指标,分别为,区间最左端(我们定义为low),区间最右端(我们定义为high),区间中点位置(我们定义为mid,注意是整数,所以不一定恰好是正中间);假设查找元素在这10个元素之中的话,那它一定介于区间最左端与区间最右端.
接下来要做的就是那8和区间中点位置对应的值去比较,因为8>5,而且这个线性表是单调递增的(5后面的元素都比5还小),所以8只可能出现在(假设出现)在6到10这个区间了,于是我们就把它设为新的区间,即把mid+1的值赋给low,这样区间就缩短一半了;循环这个过程,下一次循环,low=5,high=10,mid=8,因为顺序表中第8个元素的值恰等于8,所以我们在第二次二分查找,就找到了指定元素.
那假设顺序表为1,3,5,7,9,11寻找元素的值为8呢?第一次判断low=1,high=6,mid=3,因为5<8,所以第二次low=4,high=6,mid=5;因为9>8,所以第三次同理要把mid-1的值赋给high,则:low=4,high=4,mid=4;因为7<8,所以第四次,low=5,high=4,但我们知道low是区间最左端,high是区间最右端,不应该出现最左端比最右端大的情况,所以当出现low>high,则判断无法找到.

先给出二分查找的算法代码:

while (low <= high) {
  mid = (low + high) / 2;
  if (a[mid] > k) // 查找左子表
   high = mid - 1;
  else if (a[mid] < k) // 查找右子表
   low = mid + 1;
  else
   break; // found
 }
 if (low<=high)
  printf("found in %dth position\n", low);
 else
  printf("not found\n");

再给出这道题的答案

Position BinarySearch(List L, ElementType X)
{
 int low = 1, high = L->Last,mid;
 while (low <= high)
 {
  mid = (low + high) / 2;
  if (L->Data[mid] == X) return mid;
  else if (L->Data[mid] >X)
   high = mid-1;//注意是mid-1
  else low = mid+1;//注意是mid+1
 }
 return NotFound;
}

再给出测试点及结果:

二分查找_详解[原理+题目]

二分查找_详解[原理+题目]

6-1 二分查找 （20 point(s))

相关推荐

6-1 二分查找（20 point(s))