<>二分查找

注:本题目源自《浙江大学-数据结构》课程,题目要求实现二分查找算法。

<>函数接口定义
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。

<>测试程序样例 (C语言版)##
#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
<>程序代码:
Position BinarySearch( List Tbl, ElementType K ) { if(Tbl==NULL) return
NotFound; int low=1,high=Tbl->Last; int mid; while(low<=high)//low一定小于等于high
如下标为1、2、3 要查询的是下标为1的数,第一次是比较下标为2的数,不符合 high就变成了1,如果写low<high就会返回错误的结果 {
mid=(low+high)/2; if(Tbl->Data[mid]==K) return mid; else if(Tbl->Data[mid]>K)
high=mid-1; else low=mid+1; } return NotFound; }
##测试结果与题目裁判结果相符

##二分查找总结:

*
概念
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
该算法充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log
n)完成搜索任务。它的基本思想是,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如
果x小于a[n/2],则我们只要在数组a的左半部继续搜索x(这里假设数组元素呈升序排列)。如果x大于a[n/2],则我们只要在数组a的右 半部继续搜索x。
*
查找过程
首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较
,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

*
算法要求
1、线性表必须采用顺序存储结构
2、表中元素按照关键字有序排列(升序或者降序)

*
比较次数
计算公式:a<log2n<b(a,b,n为正整数)a<log2n<b (a,b,n为正整数)a<log2n<b(a,b,n为正整数)
当顺序表有n个关键字时:
查找失败时,至少比较a次关键字;查找成功时,最多比较关键字次数是b。
注意:a,b,n均为正整数。

*
Python源码
def bin_search(data_list, val): low = 0 # 最小数下标 high = len(data_list) - 1 #
最大数下标 while low <= high: mid = (low + high) // 2 # 中间数下标 if data_list[mid] ==
val: # 如果中间数下标等于val, 返回 return mid elif data_list[mid] > val: # 如果val在中间数左边,
移动high下标 high = mid - 1 else: # 如果val在中间数右边, 移动low下标 low = mid + 1 return #
val不存在, 返回None ret = bin_search(list(range(1, 10)), 3) print(ret)
* C/C++递归实现 #include<iostream> using namespace std; int
a[100]={1,2,3,5,12,12,12,15,29,55};//数组中的数(由小到大) int k;//要找的数字 int found(int
x,int y) { int m=x+(y-x)/2; if(x>y)//查找完毕没有找到答案,返回-1 return -1; else {
if(a[m]==k) return m;//找到!返回位置. else if(a[m]>k) return found(x,m-1);//找左边 else
return found(m+1,y);//找右边 } } int main() { cin>>k;//输入要找的数字c语言把cin换为scanf即可
cout<<found(0,9);//从数组a[0]到a[9]c语言把cout换为printf即可 return 0; }
##函数运行时间计时程序模板
#include <iostream> #include <time.h> //For using the system Timer #include
<stdlib.h> using namespace std; clock_t start, stop; //Define the start and
stop of the timer int PrintN(int n) { int i = 0; for (i; i < n; i++) {
std::cout << i << endl; } return 0; } int main() { int n; std::cin>>n; start =
clock(); PrintN(n); stop = clock(); double duration = ((double)(stop - start))
/ CLK_TCK; //To calculate the time that this function used std::cout <<
duration << endl; system("PAUSE"); //Pause the system for a moment return 0; }

技术
©2019-2020 Toolsou All rights reserved,
华为认证HCIA-AI人工智能NOI2019 游记消息质量平台系列文章|全链路排查篇过拟合和欠拟合的形象解释Unity 场景异步加载(加载界面的实现)Faster RCNN系列算法原理讲解(笔记)纽约年轻人计划“重新占领华尔街”:维护散户利益用C++跟你聊聊“原型模式” (复制/拷贝构造函数)初识python之技巧总结篇中级JAVA程序员应该掌握的数据结构知识