当前位置:   article > 正文

二分查找法的递归和非递归实现(C++)_递归改为非递归 c++

递归改为非递归 c++

1.二分查找法思想

折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用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。[引自百度百科]

2.算法使用前提

1.必须采用顺序存储结构。
2.必须按关键字大小有序排列。

注:顺序存储结构-------逻辑上相邻的结点存储在物理位置上相邻的存储单元中,比如数组等结构

3.递归实现(C++)

#include <iostream>
using namespace std;
//二分查找发C++实现
int binarySearch(int a[], int x, int left, int right);//函数声明
int main()
{
   
	int a[] = {
   1,2,3,4,5,6,7,8,9};
	//int mark = binarySearch(a, 6, 0, sizeof(a)/sizeof(a[0]) - 1);//sizeof(a)/sizeof(a[0])为数组a的长度
	int mark = binarySearch(a, 11
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
本文内容由网友自发贡献,转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/896658
推荐阅读
相关标签
  

闽ICP备14008679号