11.2 二分查找的原理及其实现

怼烎@ 2022-05-13 23:13 165阅读 0赞

![70][]

> pow(2,10)=1024,所以只需要10次。二分查找的数必须为有序的。

![70 1][]

#include<iostream>
    using namespace std;
    
    int BinarySearch(int a[], int n, int k)
    {
    	int left = 0;
    	int right = n-1;
    	while(left <= right)
    	{
    		int mid = left + (right - left)/2;
    		if(a[mid] == k)
    			return mid;
    		else if(a[mid] > k)
    			right = mid-1;
    		else 
    			left = mid + 1;			
    	} 
    	return -1;
    } 
    
    int main()
    {
    	int a[5]={1,2,5,7,9};//必须为有序的序列
    	cout << BinarySearch(a,5,7) << endl;//3 
    	return 0;
    }

![70 2][]

#include<iostream>
    using namespace std;
    
    int LowerBound(int a[], int n, int k)
    {
    	int left = 0;
    	int right = n-1;
    	int lowerk = -1;//赋初值，记录比k小的最大数的下标 
    	while(left <= right)
    	{
    		int mid = left + (right - left)/2;
    		if(a[mid] >= k)
    			right = mid - 1;
    		else
    		{
    			left = mid + 1;
    			lowerk = mid;
    		}
    	} 
    	return lowerk;
    }
    
    int main()
    {
    	int a[6] = {1,2,4,6,8,9};
    	cout << LowerBound(a,6,7) << endl;//3 
    	cout << LowerBound(a,6,9) << endl;//4
    	return 0; 
    }

![70 3][]

> L+R 的值可能很大，达到超过了int的范围，这样会导致溢出。

[70]: /images/20220514/59d86a508a4e437e82f9f345aa617d66.png
[70 1]: /images/20220514/34d067bd19fa4efca370465ff4b14646.png
[70 2]: /images/20220514/1d9d38a50ed44fe9b9052e62ffeadc1d.png
[70 3]: /images/20220514/ec48724d25fd47b782f7fd6f4b921651.png

发表评论取消回复

表情：

评论列表（有 0 条评论，165人围观）

还没有评论，来说两句吧...

相关阅读

相关二分查找的简单实现

> 简单记录了一下二分查找的实现文章目录前言一、二分查找是什么？二、代码实现总结 -------------------- 前言这天，六花来

小灰灰/ 2024年03月24日 10:56/ 0 赞/ 67 阅读

相关二分查找算法原理和实现

二分查找是一种比较高效的搜索算法，是一种可以在有序数组中搜索到特定元素的算法。例如，我们要在数组\{1,4,6,10,20\}中搜索4 1. 首先与数组的中间位置的

我会带着你远行/ 2023年06月13日 15:28/ 0 赞/ 14 阅读

相关二分查找法的实现及原理

二分搜索法原理：折半查找，直到查找到的元素与目标元素相等，查找终止二分搜索法的实现剖析：注： 1.基于排序的代码才能使用该方法 2.查找的

拼搏现实的明天。/ 2022年11月19日 09:45/ 0 赞/ 170 阅读

相关二分查找的实现

在一个有序的数组中，查找一个数，可以使用二分查找，但是这个算法也是有很多地方需要注意的。正确的写法如下所示。 int binary_search(int array,

缺乏、安全感/ 2022年08月04日 12:56/ 0 赞/ 229 阅读

相关 [查找算法]--二分查找的Java实现

> 二分查找算法思想：又叫折半查找，要求待查找的序列有序。每次取中间位置的值与待查关键字比较，如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比

骑猪看日落/ 2022年07月12日 02:58/ 0 赞/ 235 阅读

相关二分查找及其变形整理

1 二分查找　　二分查找是一个基础的算法，也是面试中常考的一个知识点。二分查找就是将查找的键和子数组的中间键作比较，如果被查找的键小于中间键，就在左子数组继续查找；如果

缺乏、安全感/ 2022年06月16日 11:42/ 0 赞/ 169 阅读

相关 11.2 二分查找的原理及其实现

![70][] > pow(2,10)=1024,所以只需要10次。二分查找的数必须为有序的。 ![70 1][] include<iostream> u

怼烎@/ 2022年05月13日 23:13/ 0 赞/ 166 阅读

相关二分查找及其变体

二分查找及其变体说到二分查找，大家肯定不陌生。就举个生活中的例子吧，相信很多人肯定玩过猜数字的游戏：大概就是我随便说一个数字，告诉你范围（比如这个数字在1到100

柔情只为你懂/ 2022年02月23日 04:26/ 0 赞/ 234 阅读

相关二分查找原理及实现

假如现在有一组1到100的数，这是一个有序的序列。现在我就从这组数里面选一个数，然后让你猜我选的数，我会告诉你是大了还是小了，最终猜到我选的数。一种方法是从1开始猜，假如我

女爷i/ 2021年11月16日 12:42/ 0 赞/ 300 阅读

相关二分查找及其相关扩展

public class BinarySearch { / @desc 二分查找，将索引返回 @par

我就是我/ 2021年09月18日 04:20/ 0 赞/ 285 阅读