龙空技术网

C++|趣味实用小程序:使用递归和非递归实现二分查找算法

小智雅汇 215

前言:

眼前姐妹们对“用非递归方法实现递归算法”大约比较注重,同学们都想要剖析一些“用非递归方法实现递归算法”的相关资讯。那么小编在网络上收集了一些关于“用非递归方法实现递归算法””的相关文章,希望大家能喜欢,咱们一起来了解一下吧!

二分查找法也称为折半查找法,它的思想是每次都与序列的中间元素进行比较。二分查找的一个前提条件是数组是有序的。

二分查找可以使用递归和非递归的方法来解决:

#include<iostream>using namespace std;int binarySearchLoop(int arr[], int len, int findData){	if(arr==NULL || len <=0)		return -1;	int start = 0;	int end = len-1;	while(start<=end)	{		int mid = start+(end-start)/2;		if(arr[mid] == findData)			return mid;		else if(findData < arr[mid])			end = mid-1;		else			start = mid+1;	}	return -1;}int binarySearchRecursion(int arr[], int findData, int start, int end){	if(arr==NULL || start>end)		return -1;		int mid = start+(end-start)/2;		if(arr[mid] == findData)			return mid;		else if(findData < arr[mid])			binarySearchRecursion(arr, findData, start, mid-1);		else			binarySearchRecursion(arr, findData, mid+1, end);}void main(){	int arr[] = {1,2,3,4,5,6,7,8};	int len = sizeof(arr)/sizeof(arr[0]);	int index = binarySearchLoop(arr,len,6);	int index2 = binarySearchRecursion(arr,6,0,len-1); cout<<index<<endl;	cout<<index2<<endl; system("pause");}/*55*/-End-

标签: #用非递归方法实现递归算法 #折半查找递归非递归