折半查找-阿里云开发者社区

开发者社区> 开发与运维> 正文
登录阅读全文

折半查找

简介:

今天在知乎上看了一个关于iOS面试题的一个问题,里面有一个题目如下:

什么是Binary Search,其时间复杂度是多少呢?

先介绍一下概念吧:

折半查找(Binary Search):又称二分查找。他的前提是线性表的记录 必须有序。

直接看代码:

复制代码
#include<stdio.h>
//a[]是要查找的顺序表,n是表的长度,found是要查找的数据  int BinarySearch(int a[],int n,int found) 
{
 //------------------------------这里最好先判断一下数组是不是为空  int low = 0;
 int high = n-1;
 int mid;
 while(low<=high) {
 mid = (low+high)/2;
// printf("-------------%d\n",mid); if(found==a[mid]) {
 return mid;
 }else if(found<a[mid]) {
 high = mid-1;
 }else {
 low = mid+1;
 }
 } 
 
 return -1;
}
int main()
{
 int found;
 int a[] = {0,1,16,24,35,47,59,62,73,88};
 int i=BinarySearch(a,10,88);
 if(i!=-1) {
 printf("在数组中的位置是:%d,\n",i);
 }else
 {
 printf("没有找到数据");
 }
 return 0;
} 
复制代码

其时间复杂度为O(logn)

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: