常见查找算法:二分查找算法
本文主要总结二分查找算法的递归实现与非递归实现,二分查找算法的时间复杂度为,且只能针对已经排好序的数组进行查找。
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;
}
上一篇: A star 算法 (Python)
下一篇: Python实现快速排序