数据结构用递归和非递归方法实现二分查找法

偏执的太偏执、 2022-07-12 04:25 227阅读 0赞

二分查找法说的通俗一点就是折半查找，每查找一次，所对应的元素就会减少一半，所以这种方法的优点就是比较的次数少，查找的速度快。但其最大的缺点就是插入数据比较困难。所以在面对数据一直会发生变动的列表，就不推荐用二分查找法了。

那么下面就来实际介绍一下这种方法，如果一个表中的元素按照由小到大来排列，找到表中间位置，并与查找的key值比较，如若相等，就说明查找成功。如果不相等，就一中间位置为准将表分为前后两部分，然后比较key值与中间值的大小，key值大，则在后半部分表中进一步查找，反之，则在前半部分表中查找。一直按此方法循环查找下去，要么查到成功，要么就说明表里没有和key值相等的数据，即查找失败。

下面就给大家分别介绍用递归和非递归方法实现二分查找法

1、用递归方式来实现

#include<iostream>
    using namespace std;
    int Find(int ar[],int low, int high, int key)
    {
    	if(low > high)
    		return -1;
    	int mid = (low+high)/2;
    	if(ar[mid] == key)
    		return mid;
    	else if(key < ar[mid])
    		return Find(ar,low,mid-1, key);
    	else
    		return Find(ar,mid+1, high, key);
    }
    void main()
    {
    	int ar[] = {1,23,45,67,90,123,345,678,900,1000};
    	int key;
        cout<<"input key:>";
    	cin>>key;
    	int n = sizeof(ar) / sizeof(int);
    	int low = 0;
    	int high = n-1;
    	int index = Find(ar,low,high,key);
    	cout<<"index = "<<index<<endl;
    }

2、用非递归方式来实现

#include<iostream>
    using namespace std;
    
    int Find(int ar[], int n, int key)
    {
    	int low = 0;
    	int high = n-1;
    	int mid;
    	while(low <= high)
    	{
    		mid = (low+high)/2;
    		if(ar[mid] == key)
    			return mid;
    		else if(key < ar[mid])
    			high = mid-1;
    		else
    			low = mid+1;
    	}
    	return -1;
    }
    void main()
    {
    	int ar[] = {1,23,45,67,90,123,345,678,900,1000};
    	int key;
        cout<<"input key:>";
    	cin>>key;
    	int n = sizeof(ar) / sizeof(int);
    	int index = Find(ar,n,key);
    	cout<<"index = "<<index<<endl;
    }

那么本次的分享也就到这了，希望能帮到大家