题目 采用二分查找法查找特定关键字的元素。要求用户输入数组长度,也就是有序表的数据长度,并输入数组元素和查找的关键字。程序输出查找成功与否,以及成功时关键字在数组中的位置。例如,在有序表11、13、18、28、39、56、69、89、98、122中查找关键字为89的元素。 1、程序分析 二分查找就是折半查找,其基本思想是:首先选取表中间位置的记录,将其关键字与给定关键字key进行比较,若相等,则查找成功;若key值比该关键值大,则要找的元素一定在右子表中,则继续对右子表进行折半查找;若key值比该关键值小,则要找的元素一定在左子表中,继续对左子表进行折半查找。如此递推,直到查找成功或查找失败(查找范围为0)。 2、程序实现
/******************************************************
* Topic : 采用二分查找法查找特定关键字的元素。
* File Name: BinarySearch.c
* Author : Jack Cui
* Created : 6 April 2016
* ****************************************************/
#include <stdio.h>
#include <stdlib.h>
/*归并排序函数声明*/
void BinarySearch(int iKey,int *pArr,int iNum);
void main(void)
{
int i,iKey,*pArr,iNum;
printf("请输入数组的长度:\n");
scanf("%d",&iNum);
printf("请输入数组元素:\n");
pArr = (int *)malloc(sizeof(int) *iNum);
for(i = 0;i < iNum;i++)
scanf("%d",&pArr[i]);
printf("请输入你想查找的元素:\n");
scanf("%d",&iKey);
BinarySearch(iKey,pArr,iNum);
}
/**********************************
*函数名称:BinarySearch
*参数说明:iKey 要查找的数
* *pArr 数组
* iNum 数组大小
*说明: 二分查找
***********************************/
void BinarySearch(int iKey,int *pArr,int iNum)
{
int iLeft,iRight,iMid,iCount,iFlag;
iCount = 0; //记录查找次数
iFlag = 0; //查找正确标志位
iLeft = 0; //左侧最小值
iRight = iNum - 1; //右侧最大值
while(iLeft <= iRight) //范围正确的时候,进行查询。
{
iCount++; //查找次数+1
iMid = (iLeft + iRight) / 2; //二分
if(iKey < pArr[iMid])
iRight = iMid - 1;
else if(iKey > pArr[iMid])
iLeft = iMid + 1;
else if(iKey == pArr[iMid])
{
printf("查找成功!\n查找%d次!pArr[%d]=%d\n",iCount,iMid,iKey);
iFlag = 1;
break;
}
}
if(iFlag == 0)
printf("查找失败!\n");
}
3、结果显示