欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

常见查找算法:二分查找算法

程序员文章站 2024-03-19 15:19:58
...

本文主要总结二分查找算法的递归实现与非递归实现,二分查找算法的时间复杂度为常见查找算法:二分查找算法,且只能针对已经排好序的数组进行查找。

1.非递归的实现:

常见查找算法:二分查找算法

   1.1 首先设置3个索引,分别指向开始,结束和中间位置,即start=0,end=len-1,mid=(start+end)/2;start向右移动,end向左移动,当start>end则跳出循环,即在while(start<=end)中进行循环.

常见查找算法:二分查找算法

   1.2 在循环中首先比较find与arr[mid],若find==arr[mid],则直接return mid;若find>arr[mid],则start = mid + 1;进行下次循环。若find<arr[mid],则end= mid - 1;进行下次循环。否则返回-1;

代码如下:

//非递归进行二分查找
int Binary_Search_No_Recursion(int * arr, int len, int find_data)
{
	int start = 0, end = len - 1;
	while (start<=end)
	{
		int mid = (start + end) / 2;
		if (arr[mid]==find_data)
		{
			return mid;
		}
		else if (arr[mid] < find_data)
		{
			start = mid + 1;
		}
		else
		{
			end = mid - 1;
		}
	}
	return -1;
}

 

2.递归实现:

  2.1 原理同上,首先取出mid位置,在if中进行判断,若arr[mid]<find_data,表示待寻找的数据在中间的右边,需要改变start为mid+1,则递归执行Binary_Search_Recursion(arr, find_data, mid + 1, end);

 2.2 若arr[mid]>find_data,表示待寻找的数据在中间的左边,需要改变end为mid-1,则递归执行Binary_Search_Recursion(arr, find_data, start, mid-1);

2.3 若arr[mid]==find_data,则直接返回mid。

代码如下:

//递归进行二分查找
int Binary_Search_Recursion(int * arr, int find_data,int start, int end)
{
	int mid = (start + end) / 2;

	if (start>end)
	{
		return -1;
	}
	else if(arr[mid]<find_data)
	{
		return Binary_Search_Recursion(arr, find_data, mid + 1, end);
	}
	else if (arr[mid] > find_data)
	{
		return Binary_Search_Recursion(arr, find_data, start, mid-1);
	}
	else if (arr[mid] == find_data)
	{
		return mid;
	}
}

 

总体实现:


#include "pch.h"
#include <iostream>
using namespace std;

//非递归进行二分查找
int Binary_Search_No_Recursion(int * arr, int len, int find_data)
{
	int start = 0, end = len - 1;
	while (start<=end)
	{
		int mid = (start + end) / 2;
		if (arr[mid]==find_data)
		{
			return mid;
		}
		else if (arr[mid] < find_data)
		{
			start = mid + 1;
		}
		else
		{
			end = mid - 1;
		}
	}
	return -1;
}

//递归进行二分查找
int Binary_Search_Recursion(int * arr, int find_data,int start, int end)
{
	int mid = (start + end) / 2;

	if (start>end)
	{
		return -1;
	}
	else if(arr[mid]<find_data)
	{
		return Binary_Search_Recursion(arr, find_data, mid + 1, end);
	}
	else if (arr[mid] > find_data)
	{
		return Binary_Search_Recursion(arr, find_data, start, mid-1);
	}
	else if (arr[mid] == find_data)
	{
		return mid;
	}
}
int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int len = sizeof(arr) / sizeof(int);
	int find = 10;
	cout << Binary_Search_No_Recursion(arr,len,find) << endl;
	cout << Binary_Search_Recursion(arr, find,0,len-1) << endl;
}