二分查找算法
2023-04-18 12:35:55 时间
二分查找(也叫折半查找)是在有序列表中频繁使用到的查找算法,复杂度为O(logn)。
简单易懂的二分算法,用一个while循环解决:
1 int bin_search(int m[],int len,int goal) 2 { 3 int left=0,right=len-1; 4 int mid; 5 while(left<=right) 6 { 7 mid=(left+right)/2; 8 if(m[mid]==goal) 9 return mid; 10 else if(goal<m[mid]) 11 right=mid-1; 12 else if(goal>m[mid]) 13 left=mid+1; 14 } 15 return -666; //查找失败 16 }
下面是用递归实现的二分算法,虽然在执行效率上会慢那么一点,但更好理解记忆。
1 int binary_search(int m[],int left,int right,int goal) 2 { 3 if(left<=right) 4 { 5 int mid=(left+right)/2; 6 if(goal==m[mid]) 7 return mid; 8 else if(goal<m[mid]) 9 return binary_search(m,left,mid-1,goal); 10 else if(goal>m[mid]) 11 return binary_search(m,mid+1,right,goal); 12 } 13 else 14 return -666; 15 }
相关文章
- 简述机器学习加速器的五种类型
- 天天写CRUD的你,到了该给系统接入API网关的时候了!
- 通过Wi-Fi实现智慧城市的可持续发展
- 体验过后,我觉得ChatGPT还有待提高!
- 装修别忘埋网线 没埋网线也有招
- 云托管与其他传统托管技术相比有何优势?
- 【硬核扫盲】到底什么是相干光通信?
- 云计算市场,谁撬走了谁的蛋糕?
- 浅谈什么是云网络?
- 云计算成本节约的主要谬误
- 开源时代,红帽如何成就客户成功
- 人工智能在云计算中能起到怎样的作用?
- 成本节约:主要云谬论之一
- 网红机器人ChatGPT的另一面
- 办公室网络还能这么搭建?从入门到精通,看这里
- 2023年值得关注的五大自动化趋势
- 什么叫SSH?原理详解,看这一篇就够了!
- 云安全责任共担往往意味着无人承担
- AI将取代人类?机器人ChatGPT能测漏洞、审代码还能修bug
- 一文读懂边缘计算(Edge ML)!