数据结构之二分查找(折半查找)

数据结构之二分查找(折半查找)

1.首先我们需要将表中的元素从小到大排序，二分查找必须是有序表，所以我们需要对无序的元素排序（切记这一步很重要）

2.由于是折半查找顾名思义也就是将表中的元素拆分成一半缩小范围来查找，所以我们需要引入2个变量low和high以及mid，其中low标志每一次折半首元素，high标志位每一次折半的尾元素，mid表示为中间元素。

弄清楚了上面的2个概念的话接下来我们需要画图来演示怎么查找

【先将元素存入顺序表中】(0位置基本不放待查找元素，大多数情况放入key)

【第一次比较】

从题目中可以看出第一次查找mid=(9+!)/2=5，其值为23，因为23>18此时我们需要将high移到mid的左侧此时high=4

【第二次比较】

第二次查找的时候mid=(4+1)/2=2此时其值为14，由于14<18,所以需要将low移到mid的右边此时low=3

【第三次比较】

第三次查找mid=(3+4)/2=3，此时其值为18，由于18=【18】，也就是我们需要查找的，故查找结束。

【注意】

在这里需要补充下，首先是我们求mid，这里mid=(low+high)/2，这里的结果是向下取整

其次就是我们算出mid之后mid对应的值，如果mid对应的值大于我们需要查找的值，那么high将右移到mid的左边，如果mid对应的值小于我们需要查找的值，那么low将移到mid的右边

二分查找的框架如下：

int binarySearch(int[] nums, int key) {
    int left = 0, right = ...;

    while(...) {
        int mid = (right + left) / 2;
        if (nums[mid] == key) {
            ...
        } else if (nums[mid] < key) {
            left = ...
        } else if (nums[mid] > key) {
            right = ...
        }
    }
    return ...;
}

递归与非递归数组实现 一段无序数列的二分查找，完整代码如下：

#include

using namespace std;
typedef long long ll;
const int N=1e3+10;
int a[N],n,key;
//排序 
void Order(int a[],int n)
{
	int t;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n-i-1;j++)
		{
			if(a[j]>a[j+1])
			{
				t=a[j];a[j]=a[j+1];a[j+1]=t;
			}
		}
	}
}
//非递归 
int Search1(int a[],int key)
{
	int low=1,high=n;
	int mid;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(a[mid]==key)return mid;
		else if(a[mid] 
图片讲解参考【数据结构】折半查找（二分查找） - 程序员大本营
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5658130.html