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

    万次阅读 多人点赞 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;
    }
     

    运行截图:

    查找在数组中的元素

     

    查找不在数组中的元素:

    展开全文
  • Java有序表查找:折半查找二分查找、差值查找和斐波那契查找  【尊重原创,转载请注明出处】http://write.blog.csdn.net/postedit?ticket=ST-84189-RPiSkdLK6Dt1Oyqsgvsx-passport.csdn.net  目前查找方法...

    Java有序表查找:折半查找、二分查找、差值查找和斐波那契查找

        【尊重原创,转载请注明出处】http://blog.csdn.net/guyuealian/article/details/51106238
         目前查找方法主要:顺序查找、有序查找(分为:折半查找即二分查找、差值查找和斐波那契查找方法)、线性索引查找、二叉排序树、平衡二叉树(AVL树)以及多路查找树(B树)、散列表查找(哈希表)等查找方法
         【1】顺序查找:是最简单的查找方法,其时间复杂度为O(n),是通过构造一个线性表,采用遍历的方法,将记录与关键字一个一个的对比,若相等则查找成功,若全都不相等,则查找失败即记录不存在;
         【2】有序查找顺序表的记录一般是无序,而有序表的记录是有序的;使用有序表查找方法时,前提条件是待查找的记录必须是已经排好序的。 有序查找分为:折半查找即二分查找、差值查找和斐波那契查找方法
          (1)
    折半查找法:又称二分查找,是最经典的有序表查找,它的前提是线性表中的记录必须是有序的(通常从小到大排列),线性表采用顺序存储的方式;其基本思路是:将关键字key与中间记录((low+high)/2)进行比较;若相等,则查找成功;若关键字小于中间记录,则说明关键字可能在下半区;若大于,则说明关键字可能在上半区;不断重复上述过程,直到查找成功或失败;
           Java代码如下:
    package javatest1;
    public class JavaTest1 {
    	public static void main(String[] args) {
    		int[] num = { 1, 2, 3, 4, 5, 6 };//必须有序
    		int index = Binary_Search(num, 5);
    		System.out.print(index);
    	}
    	/* num:有序表(由小到大排列)
    	 * key:要查找的关键字
    	 * return:还回查找到关键字的下标,没有找到则还回-1
    	 */
    	private static int Binary_Search(int[] num, int key) {
    		int low, high, mid;
    		low = 0;
    		high = num.length - 1;
    		while (low <= high) {
    			mid = (low + high) / 2;
    			if (key < num[mid])
    				high = mid - 1;
    			else if (key > num[mid])
    				low = mid + 1;
    			else// 如果等于则直接还回下标值
    				return mid;
    		}
    		return -1;
    	}
    }
          (2)插值查找:对二分法查找进行改进,将要查找的关键字key与查找表中的最大最小值记录进行比较后,再确定查找的范围。在二分法查找中,是以中间记录作为查找分区的,即将表一分为二,分为上下两个查找分区:
          而插值查找采用插值公式的方法,来确定查找分区。可简单这样理解,比如有100个数其值在0~1000范围之间从小到大排序,你要查找关键字为5的位置下标,若采用二分法,则大概在500的地方往下查找,但采用插值的方法,可以通过插值计算出5这个关键字应该在靠近0的地方,因此查找时从50往下开始查找,从而提高效率:


          因此插值查找只需要在折半查找算法的代码中简单修改一下即可:
    package javatest1;
    public class JavaTest1 {
    
    	public static void main(String[] args) {
    		int[] num = { 1, 2, 3, 4, 5, 6 };// 必须有序
    		int index = Insert_Search(num, 5);
    		System.out.print(index);
    	}
    	/*
    	 * num:有序表(由小到大排列) key:要查找的关键字 return:还回查找到关键字的下标,没有找到则还回-1
    	 */
    	private static int Insert_Search(int[] num, int key) {
    		int low, high, mid;
    		low = 0;
    		high = num.length - 1;
    		while (low <= high) {
    			// mid = (low + high) / 2;//二分查找
    			mid = low + (high - low) * (key - num[low])/ (num[high] - num[low]); // 插值查找
    			if (key < num[mid])
    				high = mid - 1;
    			else if (key > num[mid])
    				low = mid + 1;
    			else
    				// 如果等于则直接还回下标值
    				return mid;
    		}
    		return -1;
    	}
    }
    


    展开全文
  • 折半查找(Binary Search)技术,又称为二分查找。它的前提是线性表中的记录必须是关键码有序(通常从小到大有序),线性表必须采用顺序存储。折半查找的基本思想是:在有序表中,取中间记录作为比较对象,若给定值与...

    1.折半查找定义

    折半查找(Binary Search)技术,又称为二分查找。它的前提是线性表中的记录必须是关键码有序(通常从小到大有序),线性表必须采用顺序存储。折半查找的基本思想是:在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键字相等,则查找成功;若给定值小于中间记录的关键字,则在中间记录的左半区继续查找;若给定值大于中间记录的关键字,则在中间记录的右半区继续查找。不断重复上述过程,直到查找成功,或所有查找区域无记录,查找失败为止。

    2.折半查找算法

    一个有序表数组{0,1,16,24,35,47,59,62,73,88,99},除0下标外共10个数字。对它进行查找是否存在62这个数。折半查找算法如下所示:

    /*折半查找*/
    int Binary_Search(int *a,int n,int key)
    {
        int low,high,mid;
        low=1;  //定义最低下标为记录首位
        high=n; //定义最高下标为记录末位
        while(low<=high)
        {
            mid=(low+high)/2;   //折半
            if(key<a[mid])  //若查找值比中值小
                high=mid-1; //最高下标调整到中位下标小一位
            else if(key>a[mid]) //若查找值比中值大
                low=mid+1;  //最低下标调整到中位下标大一位
            else
                return mid; //若相等则说明mid即为查找到的位置
        }
        return 0;
    }

    上述代码的具体执行流程

    1.程序开始运行,参数a={0,1,16,24,35,47,59,62,73,88,99},n=10,key=62,第3~5行,此时low=1,high=10,如下图所示:

    2.6~15行循环,进行查找

    3.第8行,mid计算得到5,由于a[5]=47 < key,所以执行了第12行,low=5+1=6,如下图所示:

    这里写图片描述

    4.再次循环,mid=(6+10)/2=8,此时a[8]=73>key,所以执行第10行,high=8-1=7,如下图所示:

    5.再次循环,mid=(6+7)/2=6,此时a[6]=59 < key,所以执行12行,low=6+1=7,如下图所示:

    这里写图片描述

    6.再次循环,mid=(7+7)/2=7,此时a[7]=62=key,查找成功,返回7。

    3.折半查找实现(Java)

    实现的目录结构

    折半查找类

    package com.red.binary.search;
    
    public class BinarySearch {
    
        public int binarySearch(int[] arr, int key) {
    
            int low = 0; 
            int high = arr.length-1;
            while(low<=high) {
                int middle = (low+high)/2;
                if(arr[middle]==key) {
                    return middle;
                }else if(arr[middle] > key) {//如果中间值大于key,则说明要在中间值左边去找key,即high=middle-1
                    high = middle-1;
                }else {
                    low=middle+1;
                }
    
            }
            return -1;
        }
    
    }

    测试类

    package com.red.binary.search;
    
    public class BinarySearchTest {
    
        public static void main(String[] args) {
            int[] arr = new int[]{1,16,24,35,47,59,62,73,88,99};
            BinarySearch bs = new BinarySearch();
            int search = bs.binarySearch(arr, 62);
            System.out.println("key所在位置:" + search);
        }
    
    }

    输出结果

    key所在位置:6
    

    4.折半查找复杂度分析

    该算法的效率非常高,但到底高多少?关键在于此算法的时间复杂度分析。首先,我们将这个数组的查找过程绘制成一棵二叉树,如下图所示,从图上就可以理解,如果查找的关键字不是中间记录47的话,折半查找等于是把静态有序查找表分成了两棵子树,即查找结果只需要找其中的一半数据记录即可,等于工作量少了一半,然后继续折半查找,效率当然是非常高了。

    根据二叉树的性质,具有n个结点的完全二叉树的深度为log2n+1。在这里尽管折半查找判定二叉树并不是完全二叉树,但同样可以得出,最坏情况是查找到关键字或查找失败的此时为log2n+1。因此最终我们折半查找算法的时间复杂度为O(logn),它显然远远好于顺序查找的O(n)时间复杂度了。

    不过由于折半查找的前提条件是需要有序表顺序存储,对于静态查找表,一次排序后不再变化,这样的算法已经比较好了。但对于需要频繁执行插入或删除操作的数据集来说,维护有序的排序会带来不小的工作量,那就不建议使用。

    展开全文
  • 折半查找,也称为二分查找。其要求是数据是有序的,即表中元素按关键字有序。 比如有序表是递增有序的。首先取这表中的中间的数据与关键值(给定值key)比较的关系。若key&gt;表的中间值,则说明key存在于表的...

    折半查找

    折半查找,也称为二分查找。其要求是数据是有序的,即表中元素按关键字有序。

    比如有序表是递增有序的。首先取这表中的中间的数据与关键值(给定值key)比较的关系。若key>表的中间值,则说明key存在于表的中间值的右侧。因此,中间值右侧的区间又要取出中间值再与key比较,以此类推,直至查找成功或者区间缩小为0时还找不到就结束。

    若key有与表中某区间 的中间值相等,则说明查找成功。

    若表的区间缩小为0时,仍然没有找到与key相匹配的值,就说明key不在表中。

    特点:只适合用于顺序存储结构,而不适用于链式存储结构。表必须要求是有序表

    时间复杂度:

    O(log2(n))

     

    折半查找的基本思路:

    优点:效率高,平均性能好

    缺点:插入删除困难

    代码:

    (1)

    #include<stdio.h>
    #define MAXL 10
    typedef struct
    {
    	int key;
    }NodeType;
    typedef NodeType SeqList[MAXL];
    int BinSearch(SeqList r,int n,int k)
    {
    	int left=0,right=n-1,mid;
    		printf("\n中间值:");
    	while(left<=right)
    	{
    		mid=(left+right)/2;
    			printf("%d  ",mid);
    		if(r[mid].key==k)
    		{
    		
    				return mid;
    		}
    		
    		if(r[mid].key>k)
    			right=mid-1;
    		else
    			left=mid+1;
    	}
    	return -1;
    }
    void main()
    {
    	SeqList r;
    	int k=7;
    	int a[10]={0,1,2,3,4,5,6,7,8,9},i,n=10;
    	for(i=0;i<n;i++)
    		r[i].key=a[i];
    	printf("关键字序列:");
    	for(i=0;i<n;i++)    
    	{
    		printf("%d  ",r[i].key);
    	}
    	if((i=BinSearch(r,n,k))!=-1)
    		printf("\n元素%d的位置是%d\n",k,i);
    	else
    		printf("元素%d不在表中\n",k);
    }

     

    (2)

    #include<stdio.h>
    int BinSearch(int arr[],int n,int k)
    {
    	int left=0,right=n-1,mid;
    		printf("\n中间值:");
    	while(left<=right)
    	{
    		mid=(left+right)/2;
    			printf("%d  ",mid);
    		if(arr[mid]==k)
    		{
    		
    				return mid;
    		}
    		
    		if(arr[mid]>k)
    			right=mid-1;
    		else
    			left=mid+1;
    	}
    	return -1;
    }
    void main()
    {
    
    	int k=7;
    	int a[10]={0,1,2,3,4,5,6,7,8,9},i,n=10;
    	printf("关键字序列:");
    	for(i=0;i<n;i++)    
    	{
    		printf("%d  ",a[i]);
    	}
    	if((i=BinSearch(a,n,k))!=-1)
    		printf("\n元素%d的位置是%d\n",k,i);
    	else
    		printf("元素%d不在表中\n",k);
    }

     

    展开全文
  • 又称二分查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有 序列表。首先,假设表中元素是按升序排列,将表中间...
  • 折半查找(二分查找)

    2014-05-07 11:03:12
    package arrays; public class HalfSerch { /* * 1,要查找的数据源必须采用顺序... //折半查找也叫半查找,该方法查找的条件必须是:查找的数组必须是有序的。 public static int halfSerch(int[] arr,int key
  • java实现二分查找折半查找

    万次阅读 2019-04-02 10:18:31
    算法思想:要求待查找的序列有序。每次取中间位置的值与待查关键字比较,如果中间位置的值比待查关键字大,则在前半部分循环这个查找的过程,如果中间位置的值比待查关键字小,则在后半部分循环这个查找的过程。直到...
  • C语言 折半查找二分查找

    千次阅读 2015-10-25 10:03:10
    折半查找
  • 折半查找跟普通的顺序查找的区别是:折半查找要求表中的元素是有序的,并且是采用顺序存储的,不能是链式存储的。 折半查找的主要思路是:在有序的表中,取得表中的中间记录进行比较。如果给定查找的值和中间记录...
  • 本题要求采用折半查找的思想,每次搜索原来数据的一半,直到搜索成功或待搜索数据为空。 1.1 输入格式 输入一个列表A和查找的值B。 1.2 输出格式 如果查找成功输出数B在列表A中的位置,否则输出查找不成功。 1.3 输....
  • 二分查找

    千次阅读 2017-01-05 13:42:49
    二分查找
  • 有序表查找_折半查找(二分查找)

    千次阅读 2013-03-06 10:34:14
    二分查找前提是线性表中的记录初始有序。时间复杂度O(logn) 代码如下: #include using namespace std; int Binary_Search(int *a, int n, int key) { int mid = 0; int high = n-1; int low = 0; while...
  • 折半查找//二分查找

    2019-12-06 09:40:40
    程序代码: #include<iostream> #include<cstdio> #include<algorithm> using namespace std; #define N 1001 int n,x,a[N]; int search(int a[],int n,int x) ... int low=0,hi...
  • JavaScript实现折半查找二分查找

    千次阅读 2017-11-26 21:38:36
    在一个升序数组中,使用折半查找得到要查询的值的索引位置。如: var a=[1,2,3,4,5,6,7,8,9]; search(a,3);//返回2 search(a,1);//左边界,返回0 search(a,9);//右边界,返回8 search(a,0);//比最小的值还小,返回...
  • 二分查找折半查找排序

    千次阅读 2016-09-10 09:34:25
    在一个有序的数组中,折半查找一个元素key,如果能找到... * 二分查找法 * @author jcm * 2016年8月6日 */ public class BinarySerach { public static void main(String[] args) { int a[] = {13,19,32,35,56
  • 二分查找折半查找

    2017-05-15 14:34:20
    * 折半查找 :首先数组是已经排好序的 * * @author zhanghaohao * @date 2017/5/15 */public class HalfDivision { /** * 循环实现 * * @param array 排好序的数组 * @param value 查找
  • 博主声明: 转载请在开头附加本文链接及作者信息... 我们学习数据结构与算法时,肯定会学到过折半查找,它也称作二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。这里有一个前提:有序数组,必须牢记。 ...
  • 折半查找二分查找)Java实现

    千次阅读 2012-07-27 22:14:12
    二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。 package ...
  • 折半查找算法折半查找(Binary Search)又称为二分查找,其要求数据序列呈线性结构,也就是经过排序的。对于没有经过排序的,可以查阅我之前的排序算法文章进行预排序,然后进行折半查找操作。譬如数组{1,2, 3, 4,...
  • 简单的折半查找方法public static int binSearch(int[] arr, int first ,int last, int target) { int mid; int midValue; while(first ){ mid = (first + last) / 2; midValue = arr[mid];

空空如也

1 2 3 4 5 ... 20
收藏数 50,800
精华内容 20,320
关键字:

折半查找