二分查找 订阅
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。 [1] 展开全文
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。 [1]
信息
外文名
Binary Search
提出时间
1946
别    称
折半查找
提出者
John Mauchly
应用学科
计算机
中文名
二分查找
适用领域范围
编程语言
缺    点
待查表为有序表
优    点
查找速度快
时间复杂度
O(log2n) [1]
二分查找查找过程
首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
收起全文
精华内容
参与话题
问答
  • [数据结构]二分查找

    万次阅读 多人点赞 2018-06-03 20:23:29
    二分查找适用于有序的顺序表,基本的思路是:首先将给定的关键字key与表array的中间位置的元素进行比较。如果相等,则查找成功,如果不登,则查找的元素一定在表的前半部分或者后半部分。继续缩小范围再进行同样的...

    #思路#

    二分查找适用于有序的顺序表,基本的思路是:首先将给定的关键字key与表array的中间位置的元素进行比较。如果相等,则查找成功,如果不相等,则查找的元素一定在表的前半部分或者后半部分。继续缩小范围到前半部分或者后半部分再进行同样的查找,直到找到为止,或者查完之后仍然没有找到元素。下面给出一次算法的查找过程实例:

    #实例#

    假设数组array为[7,10,13,16,19,29,32,33,37,41,43],要查找的元素为11:
    这里写图片描述
    #代码#

    #include <iostream>
    #include <vector>
    using namespace std;
    class Solution
    {
    public:
    	int binarySearch(vector<int> nums, int val)
    	{
    		int low = 0, high = nums.size() - 1, mid;
    		while (low <= high)
    		{
    			mid = (low + high) / 2;
    			if (nums[mid] == val)
    			{
    				return mid;
    			}
    			else if (nums[mid] > val)
    			{
    				high = mid - 1;
    			}
    			else
    				low = mid + 1;
    		}
    		return -1;
    	}
    };
    

    #复杂度#
    时间复杂度为O(log₂n),空间复杂度为O(1)

    展开全文
  • 二分查找

    千次阅读 2017-05-06 14:17:42
    二分查找是一种效率非常高的查询算法,其简单思想是:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后;将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于...

    二分查找是一种效率非常高的查询算法,其简单思想是:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后;将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回。然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分

    这里给出二分查找算法的Java实现:

    int BinSearch(int Array[],int low,int high,int key)
    {
        if (low<=high)
        {
            int mid = (low+high)/2;
            if(key == Array[mid])
                return mid;
            else if(key<Array[mid])
                //移动low和high
                return BinSearch(Array,low,mid-1,key);
            else if(key>Array[mid])
                return BinSearch(Array,mid+1,high,key);
        }
        else
            return -1;
    }

    最近看到A到一道题,已知一个数组是递增或者递减,或者是递增递减交错,求该数组的峰值,算法要求时间复杂度在O(logn), 有思路的可以在评论区留言,大家一起讨论,谢谢!

    展开全文
  • C实现二分查找

    千次阅读 2018-07-29 12:54:02
    二分查找又称折半查找,对排好序的数组,每次取这个数和数组中间的数进行比较,复杂度是O(logn)如:设数组为a[n],查找的数x, 如果x==a[n/2],则返回n/2; 如果x &lt; a[n/2],则在a[0]到a[n/2-1]中进行查找; ...

    原文链接:链接

    简要描述

    二分查找又称折半查找,对排好序的数组,每次取这个数和数组中间的数进行比较,复杂度是O(logn)如:设数组为a[n],查找的数x,

    如果x==a[n/2],则返回n/2;

    如果x < a[n/2],则在a[0]到a[n/2-1]中进行查找;

    如果x > a[n/2],则在a[n/2+1]到a[n-1]中进行查找;

    优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。

    条件:查找的数组必须要为有序数组。

     

    二种实现方式

     

    1.递归

     

    
     
    1. /*

    2. 归的二分查找

    3. arrat:数组 , low:上界; high:下界; target:查找的数据; 返回target所在数组的下标

    4. */

    5. int binarySearch(int array[], int low, int high, int target) {

    6. int middle = (low + high)/2;

    7. if(low > high) {

    8. return -1;

    9. }

    10. if(target == array[middle]) {

    11. return middle;

    12. }

    13. if(target < array[middle]) {

    14. return binarySearch(array, low, middle-1, target);

    15. }

    16. if(target > array[middle]) {

    17. return binarySearch(array, middle+1, high, target);

    18. }

    19. }


     

    2.非递归(循环)

     

    
     
    1. /*

    2. 非递归的二分查找

    3. arrat:数组 , n:数组的大小; target:查找的数据; 返回target所在数组的下标

    4. */

    5. int binarySearch2(int array[], int n, int target) {

    6. int low = 0, high = n, middle = 0;

    7. while(low < high) {

    8. middle = (low + high)/2;

    9. if(target == array[middle]) {

    10. return middle;

    11. } else if(target < array[middle]) {

    12. high = middle;

    13. } else if(target > array[middle]) {

    14. low = middle + 1;

    15. }

    16. }

    17. return -1;

    18. }


     

    推荐使用非递归的方式,因为递归每次调用递归时有用堆栈保存函数数据和结果。能用循环的尽量不用递归。

     

    二分查找的应用

    还是对上一篇博文《C++如何跳出多层循环》中提到的抽签问题进行分析。

    上一篇博文中是进行了四重循环的嵌套,基时间复杂度是O(n4),数据大时其计算量会大的惊人。为便于分析,将之前代码帖至如下:

     

    
     
    1. **

    2. 抽签问题

    3. 解决方案,复杂度n^4

    4. */

    5. void drawLots() {

    6. //从标准输入读入

    7. int numOfCard, sum;

    8. int k[MAX_N];

    9. cout<<"输入numOfCard和sum"<<endl;

    10. cin>>numOfCard>>sum;

    11. cout<<"请输入这sum张卡片的数字"<<endl;

    12. for(int i=0; i<numOfCard; i++) {

    13. cin>>k[i];

    14. }

    15. bool result = false;

    16. bool isBreakLoop = true;

    17. int _sum = 0;

    18. for(int a = 0; a < numOfCard && isBreakLoop; a ++) {

    19. for(int b = 0; b < numOfCard && isBreakLoop; b ++) {

    20. for(int c = 0; c < numOfCard && isBreakLoop; c++) {

    21. for(int d = 0; d < numOfCard && isBreakLoop; d ++) {

    22. _sum = k[a] + k[b] + k[c] + k[d];

    23. if(_sum == sum) {

    24. result = true;

    25. isBreakLoop = false;

    26. }

    27. }

    28. }

    29. }

    30. }

    31. cout << "_sum:" << _sum << " " << "sum:" << sum << endl;

    32. if(result){

    33. cout<<"Yes"<<endl;

    34. } else

    35. cout<<"No"<<endl;

    36. }

    最内层循环所做事如下:

    Ka + kb + kc + kd = m

    移项后如下:

    Kd = m - (Ka + kb + kc)

    到第四层循环时,其实Ka ,kb,kc已经知道,那问题也就变成了对kd的查找,我们可用上面讲的二分查找,复杂度就降为O(n3logn).实现如下:

    降低复杂度的实现

     

    
     
    1. /**

    2. 抽签问题

    3. 解决方案,复杂度n^3 * log(n)

    4. */

    5. void drawLots2() {

    6. int numOfCard, sum;

    7. int k[MAX_N];

    8. cout<<"输入numOfCard和sum"<<endl;

    9. cin>>numOfCard>>sum;

    10. cout<<"请输入这sum张卡片的数字"<<endl;

    11. for(int i=0; i<numOfCard; i++) {

    12. cin>>k[i];

    13. }

    14. //对数组进行排序

    15. sort(k, k + numOfCard);

    16. int index = -1;

    17. bool isBreakLoop = true;

    18. for(int a = 0; a < numOfCard && isBreakLoop; a ++) {

    19. for(int b = 0; b < numOfCard && isBreakLoop; b ++) {

    20. for(int c = 0; c < numOfCard && isBreakLoop; c++) {

    21. index = binarySearch2(k, numOfCard, sum - (k[a] + k[b] + k[c]));

    22. if(index >= 0) {

    23. isBreakLoop = false;

    24. }

    25. }

    26. }

    27. }

    28. if(index >= 0){

    29. cout<<"Yes"<<endl;

    30. } else

    31. cout<<"No"<<endl;

    32. }

    进一步优化[O(n2logn)]

    根据上一步的优化方式,我们可以进一步对内侧两层循环(也就是第三层和第四层)进行思考:

    Kc+ kd = m - (Ka + kb )

    我们不能直接对Kc+ kd进行查找,但是可以预先枚举出Ka + kb 的n2种数值并排序,再对Kc+ kd进行十分查找。列出枚举O(n2),排序O(n2logn), 循环O(n2logn),所以总的复杂度降为O(n2logn),实现如下:

     

    
     
    1. /**

    2. 抽签问题

    3. 解决方案,复杂度n^2 * log(n)

    4. */

    5. void drawLots3() {

    6. int numOfCard, sum;

    7. int k[MAX_N];

    8. cout<<"输入numOfCard和sum"<<endl;

    9. cin>>numOfCard>>sum;

    10. cout<<"请输入这sum张卡片的数字"<<endl;

    11. for(int i=0; i<numOfCard; i++) {

    12. cin>>k[i];

    13. }

    14. int cdNum = numOfCard*(numOfCard+1)/2;

    15. int cdSum[cdNum];

    16. int i = 0;

    17. for(int a=0; a<numOfCard; a++) {

    18. for(int b=i; b<numOfCard; b++) {

    19. cdSum[i ++] = k[a] + k[b];

    20. }

    21. }

    22. //对数组进行排序

    23. sort(cdSum, cdSum + cdNum);

    24. int index = -1;

    25. bool isBreakLoop = true;

    26. for(int a = 0; a < numOfCard && isBreakLoop; a ++) {

    27. for(int b = 0; b < numOfCard && isBreakLoop; b ++) {

    28. for(int c = 0; c < numOfCard && isBreakLoop; c++) {

    29. index = binarySearch2(cdSum, cdNum, sum - (k[a] + k[b]));

    30. if(index >= 0) {

    31. isBreakLoop = false;

    32. }

    33. }

    34. }

    35. }

    36. if(index >= 0){

    37. cout<<"Yes"<<endl;

    38. } else

    39. cout<<"No"<<endl;

    40. }

    进一步思考

    上面枚举Ka + kb 时其实是有重复的,因为k[i] + k[j] == k[j] + k[i],去除重复值之后,Ka + kb 值的个数是n(n+1)/2。至于n(n+1)/2怎么来,可以简单推导如下:

    N     M

    1     1

    2      2+1

    3     3+2+1

    4     4+ 3+2+1

    ......

    实现如下:

     

    
     
    1. /**

    2. 抽签问题

    3. 解决方案,复杂度n^2 * log(n)

    4. */

    5. void drawLots3_1() {

    6. int numOfCard, sum;

    7. int k[MAX_N];

    8. cout<<"输入numOfCard和sum"<<endl;

    9. cin>>numOfCard>>sum;

    10. cout<<"请输入这sum张卡片的数字"<<endl;

    11. for(int i=0; i<numOfCard; i++) {

    12. cin>>k[i];

    13. }

    14. int cdNum = numOfCard*numOfCard;

    15. int cdSum[cdNum];

    16. for(int a=0; a<numOfCard; a++) {

    17. for(int b=0; b<numOfCard; b++) {

    18. cdSum[a*numOfCard + b] = k[a] + k[b];

    19. }

    20. }

    21. //对数组进行排序

    22. sort(cdSum, cdSum + cdNum);

    23. int index = -1;

    24. bool isBreakLoop = true;

    25. for(int a = 0; a < numOfCard && isBreakLoop; a ++) {

    26. for(int b = 0; b < numOfCard && isBreakLoop; b ++) {

    27. for(int c = 0; c < numOfCard && isBreakLoop; c++) {

    28. index = binarySearch2(cdSum, cdNum, sum - (k[a] + k[b]));

    29. if(index >= 0) {

    30. isBreakLoop = false;

    31. }

    32. }

    33. }

    34. }

    35. if(index >= 0){

    36. cout<<"Yes"<<endl;

    37. } else

    38. cout<<"No"<<endl;

    39. }

    展开全文
  • 二分查找(折半查找)

    万次阅读 多人点赞 2018-07-21 00:07:47
    二分查找是一种算法,其输入是一个有序的元素列表(必须是有序的),如果查找的元素包含在列表中,二分查找返回其位置,否则返回NULL 比如说有一个1-100的数字,我随机的选择其中一个数字(假设为60),你需要以...

    二分查找是一种算法,其输入是一个有序的元素列表(必须是有序的),如果查找的元素包含在列表中,二分查找返回其位置,否则返回NULL

     

    比如说有一个1-100的数字,我随机的选择其中一个数字(假设为60),你需要以最少的次数猜到我所选择的数字,每次猜测后,我会告诉你大了,小了,对了。

    假设你第一次从1开始猜,小了

    第二次:2  小了

    第三次:3  小了

    ……

    第五十九次:59 小了

    第六十次:60 对了

    这是简单的查找,每次猜测只能排除一个数字,如果我想的数字是100,那么你可能需要从1猜到100了!

    那么有没有更好的查找方式呢?

    答案当然是有的。

    如果我选的数字是60

    第一次:你从50开始猜,那么我告诉你小了,就排除了接近一半的数字,因为你至少知道1-50都小了

    第二次:你猜75,那么我告诉你大了,这样剩下的数字又少了一半!或许你已经想到了,我们每次猜测都是选择了中间的那个数字,从而使得每次都将余下的数字排除了一半。

    第三次:接下来,很明显应该猜测63,大了

    第四次:然后你猜56,小了

    第五次:然后你猜59 小了

    第六次:猜测61,大了

    第七次,你就能很明确的告诉我,答案是60!

    这样的查找方式,很明显比第一种要高效很多。第一种需要猜测60次才能猜出正确答案,而使用第二种方式,只需要七次就能猜出正确答案

    或许看到这里你已经明白了,这就是二分查找的方法。为什么二分查找要求有序,从这里也可以看出来。一般而言,对于包含n个元素的列表,用二分查找最多需要logn步,而简单查找最多需要n步。

    #include<stdio.h>
    #include<iostream>
    using namespace std;
    int main(){ 
      int a[100];//注意这里的数组下标,即a[0]=1,a[1]=2……a[99]=100
      int guess;//猜测字符
      int flag=0;//设置标志位,区分是否查找成功
      int count=0;//统计比较次数
      int low=0,mid,high=99; 
      //初始化
      cout<<"1、初始化"<<endl;
      for(int i=0;i<100;i++){
          a[i]=i+1;
      }
      cout<<"2、要查找的数字"<<endl;
      cout<<"guess:";
      cin>>guess;
      cout<<"3、二分查找"<<endl;
      //二分查找
      while(low<=high){
    	  count++;
          mid=(low+high)/2;
    	 cout<<"第"<<count<<"次查找,其中low="<<low<<"   high="<<high<<"   mid="<<mid<<endl;
    	 if(guess==a[mid]){
    		 flag=1;
    		 cout<<"success!比较次数:"<<count<<"次"<<endl;
    		 break;//查找成功就退出,如果想要继续查找也是可以的
    	 }
    	 if(guess>a[mid]){
    		 low=mid+1;
    	 }
    	 if(guess<a[mid]){
    	      high=mid-1;
    	 }		
      }
      if(flag==0)
    	  cout<<"fail!"<<endl;
    }
     

    运行截图:

    查找在数组中的元素

     

    查找不在数组中的元素:

    展开全文
  • c++实现二分查找

    万次阅读 多人点赞 2013-11-17 22:25:57
    二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。 条件:查找的数组必须要为有序数组。 二分查找的过程剩简要描述如下图: 二种实现方式 1....
  • 算法——二分法查找(binarySearch)

    万次阅读 多人点赞 2018-04-11 14:52:35
    二分法查找,也称为折半法,是一种在有序数组中查找特定元素的搜索算法。二分法查找的思路如下:(1)首先,从数组的中间元素开始搜索,如果该元素正好是目标元素,则搜索过程结束,否则执行下一步。(2)如果目标...
  • 二分查找算法及其变种详解

    千次阅读 2019-02-15 21:11:47
    二分查找(Binary Search)算法,也叫折半查找算法,它的思想非常简单,在生活中随处可见(比如:猜字游戏),但这看似简单的算法,实际却没那么容易掌握透彻。 二分查找针对的是一个有序的数据集合,查找思想有点...
  • 二分查找算法

    千次阅读 2016-04-17 00:03:11
    书里给的第一个例子就是二分查找算法,这是个很经典的算法,晚上闲来无事,就试着用Java实现了。由于这本书的代码包含了作者及其团队封装的包(algs4.jar),我便去网上下载并导入了这个包,但是运行源代码后一直...
  • 二分查找算法 实现 def bi_search(nums, target): low = 0 high = len(nums)-1 while low &amp;amp;amp;lt;= high: mid = (low+high)//2 if target == nums[mid]: ...
  • 二分查找法(BinarySearch)算法,也叫折半查找算法二分查找针对的是一个有序的数据集合,查找思想有点类似于分治思想。每次都通过跟区间的中间元素对比,将带查找的区间缩小为之前的一半,知道找到要查找的元素,...
  • 查找算法之二分查找算法

    千次阅读 2015-07-23 08:08:49
    查找算法之二分查找算法1. 概述二分查找算法也称折半查找算法,是在有序数组中用到的较为频繁的一种查找算法。在未接触二分查找算法时,最通用的一种做法是,对数组进行遍历,跟每个元素进行比较,即顺序查找。二分...
  • [算法]二分查找算法

    千次阅读 2015-01-03 17:19:48
    二分搜索主要解决的问题是确定排序后的数组x[0,n-1]中是否包含目标元素target。 二分搜索通过持续跟踪数组中包含元素target的范围(如果target存在数组中的话)来解决问题。 一开始,这个范围是整个数组,然后通过...
  • C++实现二分查找算法

    万次阅读 2016-07-27 11:08:26
    想必二分查找很多人都不陌生,或许说很熟悉,但是在实际生活中又有很多人不能正确的写出它的相应代码,因为二分查找的边界条件等很难控制,下面我们来仔细的分析一下二分查找,这只是个人看法,如有异议,欢迎提出。...
  • 二分法查找算法的FLASH演示。 非常形容表示了二分法查找算法的实现及原理。对初学者有一定帮助。
  • 二分查找算法(递归与非递归两种方式)

    万次阅读 多人点赞 2014-04-27 15:44:26
    首先说说二分查找法。 二分查找法是对一组有序的数字中进行查找,传递相应的数据,进行比较查找到与原数据相同的数据,查找到了返回1,失败返回对应的数组下标。 采用非递归方式完成二分查找法。java代码如下所示。
  • 二分查找算法基本思想二分查找算法的前置条件是,一个已经排序好的序列(在本篇文章中为了说明问题的方便,假设这个序列是升序排列的),这样在查找所要查找的元素时,首先与序列中间的元素进行比较,如果大于这个元素,就在...
  • C#二分查找算法设计实现 1.介绍 二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。(记住了前提要求是顺序存储...
  • 二分查找算法(Java)

    千次阅读 2017-08-14 17:18:12
    1.二分查找算法思想:将n个元素分成大致相等的两部分,取a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果x2.时间复杂度:匹配k次后,剩下的元素个数为: n/(2^k) 根据 n/(2^k) >=1 , 即可求出时间复杂度 O(log2...

空空如也

1 2 3 4 5 ... 20
收藏数 566,853
精华内容 226,741
关键字:

二分查找