精华内容
下载资源
问答
  • 利用二查找法查找数据

    千次阅读 2016-12-16 14:33:47
    3.用户输入某一个数据进行查找查找到后返回该数据以及该数据的位置 4.若没有查找到则输出没有找到 代码如下: public class ErFenChaZhao { public static void main(String[] args) { //接收产生的随机数组...

    要求:

    1.随机生成15个不重复的0-100之间的整数组成数组并输出

    2.对数组进行排序

    3.用户输入某一个数据进行查找,查找到后返回该数据以及该数据的位置

    4.若没有查找到则输出没有找到

    代码如下:

    public class ErFenChaZhao {
    	public static void main(String[] args) {
    		//接收产生的随机数组
    		int[] arr = generate();
    		System.out.println("排序前数组(不重复):"+Arrays.toString(arr));
    		//数组排序
    		Arrays.sort(arr);
    		System.out.println("排序后数组(不重复):"+Arrays.toString(arr));
    		//查找数据
    		check(arr);
    	}
    	//产生随机数组0-100不重复
    	public static int[] generate(){
    		Random rand = new Random();
    		int[] arr = new int[15];
    		boolean[] flag = new boolean[100];//给这100个数安装一个开关
    		for(int i = 0;i<arr.length;i++){
    			int index;
    			do{
    				index = rand.nextInt(100);
    			}while(flag[index]);
    			flag[index] = true;
    			arr[i] = index;
    		}
    		return arr;
    	}
    	//传入参数:数组,用户输入并判断,返回查到的数据并且范围数据位置,或没有查找到该数据
    	public static void check(int[] arr){
    		Scanner scan = new Scanner(System.in);
    		System.out.println("请用户输入要查找的数据:");
    		int input = scan.nextInt();//接收数据
    		int start = 0;
    		int end =arr.length-1;
    		boolean k = false;
    		int middle = 0;
    		while(start <= end){
    			middle = (start + end)/2;
    			if(input < arr[middle]){
    				end = middle -1;
    			}else if(input > arr[middle]){
    				start = middle + 1;
    			}else{
    				k = true;
    				break;
    			}
    		}
    		if(k){
    			System.out.println("数据"+input+"位于数组的第"+(middle+1)+"个元素位置处");
    		}else{
    			System.out.println("数据"+input+"不在数组里面");
    		}
    	}
    }

    测试结果如下:

    排序前数组(不重复):[60, 24, 76, 43, 9, 17, 73, 0, 61, 75, 37, 77, 94, 96, 32]
    排序后数组(不重复):[0, 9, 17, 24, 32, 37, 43, 60, 61, 73, 75, 76, 77, 94, 96]
    请用户输入要查找的数据:
    76
    数据76位于数组的第12个元素位置处




    展开全文
  • 将做工程过程中重要的一些代码做个备份,如下的代码是关于C#使用二查找在ArrayList中查找数据的代码,希望能各位有帮助。 using System; using System.Collections; class Album : IComparable, ICloneable { ...

    将做工程过程中重要的一些代码做个备份,如下的代码是关于C#使用二分查找法在ArrayList中查找数据的代码,希望能对各位有帮助。
    using System;

    using System.Collections;

    class Album : IComparable, ICloneable {

    private string _Title;
    
    private string _Artist;
    
    
    public Album(string artist, string title) {
    
        _Artist = artist;
    
        _Title = title;
    
    }
    
    
    public string Title {
    
        get {
    
            return _Title;
    
        }
    
        set {
    
            _Title = value;
    
        }
    
    }
    
    
    public string Artist {
    
        get {
    
            return _Artist;
    
        }
    
        set {
    
            _Artist = value;
    
        }
    
    }
    
    public override string ToString() {
    
        return _Artist + ",t" + _Title;
    
    }
    
    public int CompareTo(object o) {
    
        Album other = o as Album;
    
        if (other == null)
    
            throw new ArgumentException();
    
        if (_Artist != other._Artist)
    
            return _Artist.CompareTo(other._Artist);
    
        else
    
            return _Title.CompareTo(other._Title);
    
    }
    
    public object Clone() {
    
        return new Album(_Artist, _Title);
    
    }
    

    }

    class TitleComparer : IComparer {

    public int Compare(object l, object r) {
    
        Album left = l as Album;
    
        Album right = r as Album;
    
        if ((left == null) || (right == null))
    
            throw new ArgumentException();
    
        if (left.Title != right.Title)
    
            return left.Title.CompareTo(right.Title);
    
        else
    
            return left.Artist.CompareTo(right.Artist);
    
    }
    

    }

    class Class1 {

    static void Main(string[] args) {
    
        ArrayList arr = new ArrayList();
    
    
        arr.Add(new Album("G", "A"));
    
        arr.Add(new Album("B", "G"));
    
        arr.Add(new Album("S", "A"));
    
    
        arr.Sort();
    
    
        try {
    
            foreach (Album a in arr) {
    
                Console.WriteLine(a);
    
            }
    
        } catch (System.InvalidCastException e) {
    
        }
    
    
        arr.Sort(new TitleComparer());
    
        foreach (Album a in arr) {
    
            Console.WriteLine(a);
    
        }
    
    
        Album l = new Album("L", "G");
    
        arr.Sort();
    
        int index = arr.BinarySearch(l);
    
        Console.WriteLine(index.ToString());
    
        arr.Sort(new TitleComparer());
    
        index = arr.BinarySearch(l, new TitleComparer());
    
        Console.WriteLine(index.ToString());
    
    }
    

    }

    展开全文
  • 例如,在{5,21,13,19,37,75,56,64,88 ,80,92}这个查找表使用折半查找算法查找数据之前,需要首先该表中的数据按照所查的关键字进行排序:{5,13,19,21,37,56,64,75,80,88,92}。 在折半查找之前查找...

    折半查找,也称二分查找,在某些情况下相比于顺序查找,使用折半查找算法的效率更高。但是该算法的使用的前提是静态查找表中的数据必须是有序的。

    例如,在{5,21,13,19,37,75,56,64,88 ,80,92}这个查找表使用折半查找算法查找数据之前,需要首先对该表中的数据按照所查的关键字进行排序:{5,13,19,21,37,56,64,75,80,88,92}

    在折半查找之前对查找表按照所查的关键字进行排序的意思是:若查找表中存储的数据元素含有多个关键字时,使用哪种关键字做折半查找,就需要提前以该关键字对所有数据进行排序。

    折半查找算法

    对静态查找表{5,13,19,21,37,56,64,75,80,88,92}采用折半查找算法查找关键字为 21 的过程为:


    图 1 折半查找的过程(a)

    如上图 1 所示,指针 low 和 high 分别指向查找表的第一个关键字和最后一个关键字,指针 mid 指向处于 low 和 high 指针中间位置的关键字。在查找的过程中每次都同 mid 指向的关键字进行比较,由于整个表中的数据是有序的,因此在比较之后就可以知道要查找的关键字的大致位置。

    例如在查找关键字 21 时,首先同 56 作比较,由于21 < 56,而且这个查找表是按照升序进行排序的,所以可以判定如果静态查找表中有 21 这个关键字,就一定存在于 low 和 mid 指向的区域中间。

    因此,再次遍历时需要更新 high 指针和 mid 指针的位置,令 high 指针移动到 mid 指针的左侧一个位置上,同时令 mid 重新指向 low 指针和 high 指针的中间位置。如图 2 所示:


    图 2 折半查找的过程(b)
     
    同样,用 21 同 mid 指针指向的 19 作比较,19 < 21,所以可以判定 21 如果存在,肯定处于 mid 和 high 指向的区域中。所以令 low 指向 mid 右侧一个位置上,同时更新 mid 的位置。



    图 3 折半查找的过程(3)
    当第三次做判断时,发现 mid 就是关键字 21 ,查找结束。

    注意:在做查找的过程中,如果 low 指针和 high 指针的中间位置在计算时位于两个关键字中间,即求得 mid 的位置不是整数,需要统一做取整操作。

    折半查找的实现代码:
    #include <stdio.h>
    #include <stdlib.h>
    #define keyType int
    typedef struct
    { keyType key;  
    // 查找表中每个数据元素的值 // 如果需要,还可以添加其他属性 }ElemType; typedef struct
    { ElemType *elem;  // 存放查找表中数据元素的数组 int length;     // 记录查找表中数据的总数量 }SSTable;
    // 创建查找表 void Create(SSTable **st, int length)
    { (
    *st) = (SSTable*)malloc(sizeof(SSTable)); (*st)->length = length; printf("输入表中的数据元素:\n"); // 根据查找表中数据元素的总长度,在存储时,从数组下标为 1 的空间开始存储数据 for (int i=1; i<=length; i++)
       { scanf(
    "%d", &((*st)->elem[i].key)); } }
    //折半查找算法 int Search_Bin(SSTable *ST, keyType key)
    {
    int low = 1;  //初始状态 low 指针指向第一个关键字 int high = ST->length;  //high 指向最后一个关键字 int mid; while (low <= high)
      { mid
    = (low+high) / 2;  // int 本身为整形,所以,mid 每次为取整的整数 if (ST->elem[mid].key == key)  // 如果 mid 指向的同要查找的相等,返回 mid 所指向的位置 { return mid; }
         else if(ST->elem[mid].key > key)  // 如果mid指向的关键字较大,则更新 high 指针的位置 { high = mid-1; } // 反之,则更新 low 指针的位置 else
       { low = mid + 1; } }
    return 0; } int main(int argc, const char * argv[])
    { SSTable
    *st; Create(&st, 11); getchar(); printf("请输入查找数据的关键字:\n"); int key; scanf("%d", &key); int location = Search_Bin(st, key); //如果返回值为 0,则证明查找表中未查到 key 值, if (location == 0)
       { printf(
    "查找表中无该元素"); }
       else
       { printf("数据在查找表中的位置为:%d", location); } return 0; }
    以图
    1 的查找表为例,运行结果为: 输入表中的数据元素: 5 13 19 21 37 56 64 75 80 88 92 请输入查找数据的关键字: 21 数据在查找表中的位置为:4

     

    折半查找的性能分析

    折半查找的运行过程可以用二叉树来描述,这棵树通常称为“判定树”。例如图 1 中的静态查找表中做折半查找的过程,对应的判定树如图 4:

    图 4 折半查找对应的判定树

    在判定树中可以看到,如果想在查找表中查找 21 的位置,只需要进行 3 次比较,依次和 56、19、21 进行比较,而比较的次数恰好是该关键字所在判定树中的层次(关键字 21 在判定树中的第 3 层)。

    对于具有 n 个结点(查找表中含有 n 个关键字)的判定树,它的层次数至多为:log2n + 1(如果结果不是整数,则做取整操作,例如: log211 +1 = 3 + 1 = 4 )。

    同时,在查找表中各个关键字被查找概率相同的情况下,折半查找的平均查找长度为:ASL = log2(n+1) – 1

    总结

    通过比较折半查找的平均查找长度,同前面介绍的顺序查找相对比,明显折半查找的效率要高。但是折半查找算法只适用于有序表,同时仅限于查找表用顺序存储结构表示。
    当查找表使用链式存储结构表示时,折半查找算法无法有效地进行比较操作(排序和查找操作的实现都异常繁琐)。

    转载于:https://www.cnblogs.com/ciyeer/p/9065781.html

    展开全文
  • 数据结构之二分查找法

    千次阅读 2012-11-26 20:54:09
    一、什么是二分查找法?(略) 二、二分查找法的性能分析。 二分查找法的平均查找长度是ASL=log2(n+1)-1 (n>50) ★例题: 长度为12的有序表(a1,a2,...a12)(其中ai当i时),进行折半查找,在假 定查找不成功时,...
    一、什么是二分查找法?(略)
    二、二分查找法的性能分析。
    二分查找法的平均查找长度是ASL=log2(n+1)-1 (n>50)
    ★例题:
        对长度为12的有序表(a1,a2,...a12)(其中ai<aj当i<j时),进行折半查找,在假
    定查找不成功时,关键字x<a1,x>a12以及ai<x<aj(i=1,2,..12)等情况发生的概率相等
    ,求查找不成功的平均查找长度是多少?
    解答:一、查找不成功事件的分布律为
    ....──┬──┬────┬────┬──┬──
    .... §.│x<a1│<a1,a2>.│<a2,a3>.│。。│x>a12
    ....──┼──┼────┼────┼──┼──
    .... P..│1/13│1/13....│1/13....│。。│1/13
    ....──┴──┴────┴────┴──┴──
    故查找不成功的数学期望为∑PiCi
    其中断定x<a1需查找3次
    <a1,a2>...4次
    <a2,a3>...4次
    <a5,a6>...4次
    <a4,a5>...4次
    <a3,a4>...3次
    <a6,a7>...3次
    <a7,a8>...4次
    <a8,a9>...4次
    <a10,a11>..4次
    <a9,a10>...4次
    <a11,a12>..4次
    x>a12......4次
    故E=49/13=3.77次
    上面的解法看起来很完备。但是本题很可能以填空题的形式出现,如果按上面的解法,
    则显得太笨拙了。在叙述最佳解法之前,再看一道例题。
    ★假定有序表A[1..20]上进行二分查找,则比较一次查找成功的结点数为__①__,比较三
    次成功的结点数为__②__,比较5次成功的结点数为__③__,平均查找长度为__④__。
    ....解:先给出正确答案:①1,..②4..,③5..④3.7 。其中平均查找长度可由下求得:
    
    ....设折半查找的判定树树深为n,则1→(n-1)都为满二叉树,故有
    ....depth=1→count=1
    ....depth=2→count=2
    ....depth=3→count=4
    ....depth=4→count=8
    ....depth=5→count=20-①-②-③-④=5(此句理解为结点总数减去以上各层结点数)。
    
    ....因此,第一层有一个结点,只需要查找一次即可找到,第二层有两个结点,各需要
    查找二次才能找到;第三层有4个结点,各需要查找3次;....因此总共查找次数为1*1+
    2*2+3*4+4*8+5*5=74,从而平均查找长度为3.7次。
    ◆以上是两个具有一般性的例子,它的一般性在于,我们没有给出具体的序列。仅就有
    序表中元素个数已知这一个条件进行了讨论。这就提示我们,二分查找法进行查找时,
    查找结果与所给序列具体值无关,只与其元素个数有关;具体到查找某个元素的结果,
    则只与该元素在序列中的位置有关。我们拿两个序列为例:
    ★例题:今有有序表A和有序表B,分别是:
    .....A: 1,3,5,20,21,32,57,58,60
    .....B: 1,2,3,4,7,8,18,23,26,30
    .....要查找表A中的关键字32和表B中的关键字18,需要查找几次?
    .....在上面的题中,查找次数只与它们所处的位置有关,所以结果应该是一致的。这里
    我们不给出答案。
    下面我们讨论解二分法查找有关问题的最佳解法——利用二分法查找判定树求解。
    三、二分法查找判定树
    ⒈定义见书。
    ⒉二分查找判定树的画法。
    ....设表A[l,h]是一个有序表。
    ◆一棵二分查找判定树的树形由以下步骤确定:
    ....①取m=(l+h)/2,以m为根,画出该结点;
    ....②取(l,m',m-1)为新有序表,画出m的左子树;取(m+1,m*,h)为新序列,画出右子树
    ;前述m'和m*由下式求得:
    ....m'=(l+m-1)/2;m*=(m+1+h)/2,即公式与最初求m的相同,类似递归定义。
    ....③若l=m,则该结点无左子树;若m=h则该结点无右子树;
    ....④重复上述步骤直到完成。
    ....下面给出一个有11个元素的有序表作二分法查找判树
    的示例:
    ①:m=(1+11)/2=6,画出根结点:.................................⑥
    ............................................................/...\
    ②:取(1,m',5),画出左子树,此时m'=3,即左子树根......(1,3,5)/.....\...L,m*,H
    结点号为3:..............................................③.......⑨(7,9,11)
    ......................................................../..\...../..\
    ③:取(7,m*,11),画出右子树,此时m*=9,即右.(1,1,2)./....\.../....\
    子树根结点号为9.........   ...........................①(445)④.⑦(778)⑩(10,10,11).....
    ........................................................\......\..\......\
    ④:取(1,m',2),画出结点3的左子树,此时m'=1,.........②.....⑤.⑧.....⑾.........
    即左子树根结点号为1(略去对其它结点的讨论);由于此
    时在(L,m,h)元组中,L=h=1,故此分支作图结束。
    ....在实际作图中,请参考右图中的标记方法,我曾经戏称
    它为关氏标注。它可以使用脱掉上面的步骤。
    ...→(445)属结点④,(778)属结点⑦
    ⒊二分查找判定树的应用
    →求ASL
    →求查找失败时的平均查找长度
    →求查找某结点的查找长度
    ⒋二分查找判定树树形的讨论
    若一棵二分查找判定树树深为H层,则1-(h-1)为满二叉树,第h层上第一个结点为空,
    最后一个结点为满(为什么?请读者思考)。
    ——————————————————————————————————————
    ——————————
    作者注:为帮助读者深入理解二分法查找,我在这里列出了一些基本概念,由于这些基
    本概念书上已讲得很详细,所以从略。列出来是帮读者形成一个完整轮廓,以免断章取
    义。
    视时间和反响而定,这是我数据结构解题方法第一篇,以后可能不定期推出续篇,也可
    能这是最后一篇。这个系列致力于找出一切可能的最简解题方法。
    作者声明保留一切权利。不保证全部观点正确及演算无误。
    
    
    
    ===============================================================================================

    在学习算法的过程中,我们除了要了解某个算法的基本原理、实现方式,更重要的一个环节是利用big-O理论来分析算法的复杂度。在时间复杂度和空间复杂度之间,我们又会更注重时间复杂度。

    时间复杂度按优劣排差不多集中在:

    O(1), O(log n), O(n), O(n log n), O(n2), O(nk), O(2n)

    到目前位置,似乎我学到的算法中,时间复杂度是O(log n),好像就数二分查找法,其他的诸如排序算法都是 O(n log n)或者O(n2)。但是也正是因为有二分的 O(log n), 才让很多 O(n2)缩减到只要O(n log n)。

     

    关于二分查找法

    二分查找法主要是解决在“一堆数中找出指定的数”这类问题。

    而想要应用二分查找法,这“一堆数”必须有一下特征:

    • 存储在数组中
    • 有序排列

    所以如果是用链表存储的,就无法在其上应用二分查找法了。(曽在面试被问二分查找法可以什么数据结构上使用:数组?链表?)

    至于是顺序递增排列还是递减排列,数组中是否存在相同的元素都不要紧。不过一般情况,我们还是希望并假设数组是递增排列,数组中的元素互不相同

     

    二分查找法的基本实现

    二分查找法在算法家族大类中属于“分治法”,分治法基本都可以用递归来实现的,二分查找法的递归实现如下:

    int bsearch(int array[], int low, int high, int target)
    {
    if (low > high) return -1;

    int mid = (low + high)/2;
    if (array[mid]> target)
    return binarysearch(array, low, mid -1, target);
    if (array[mid]< target)
    return binarysearch(array, mid+1, high, target);

    //if (midValue =http://www.cnblogs.com/ider/archive/2012/04/01/= target)
    return mid;
    }

     

    不过所有的递归都可以自行定义stack来解递归,所以二分查找法也可以不用递归实现,而且它的非递归实现甚至可以不用栈,因为二分的递归其实是尾递归,它不关心递归前的所有信息。

    int bsearchWithoutRecursion(int array[], int low, int high, int target)
    {
    while(low <= high)
    {
    int mid = (low + high)/2;
    if (array[mid] > target)
    high = mid - 1;
    else if (array[mid] < target)
    low = mid + 1;
    else //find the target
    return mid;
    }
    //the array does not contain the target
    return -1;
    }

     

    只用小于比较(<)实现二分查找法

    在前面的二分查找实现中,我们既用到了小于比较(<)也用到了大于比较(>),也可能还需要相等比较(==)。

    而实际上我们只需要一个小于比较(<)就可以。因为错逻辑上讲a>b和b<a应该是有相当的逻辑值;而a==b则是等价于 !((a<b)||(b<a)),也就是说a既不小于b,也不大于b。

    当然在程序的世界里, 这种关系逻辑其实并不是完全正确。另外,C++还允许对对象进行运算符的重载,因此开发人员完全可以随意设计和实现这些关系运算符的逻辑值。

    不过在整型数据面前,这些关系运算符之间的逻辑关系还是成立的,而且在开发过程中,我们还是会遵循这些逻辑等价关系来重载关系运算符。

    干嘛要搞得那么羞涩,只用一个关系运算符呢?因为这样可以为二分查找法写一个template,又能减少对目标对象的要求。模板会是这样的:

     

    template <typename T, typename V>
    inline int BSearch(T& array, int low, int high, V& target)
    {
    while(!(high < low))
    {
    int mid = (low + high)/2;
    if (target < array[mid])
    high = mid - 1;
    else if (array[mid] < target)
    low = mid + 1;
    else //find the target
    return mid;
    }
    //the array does not contain the target
    return -1;
    }

    我们只需要求target的类型V有重载小于运算符就可以。而对于V的集合类型T,则需要有[]运算符的重载。当然其内部实现必须是O(1)的复杂度,否则也就失去了二分查找的效率。

     

    用二分查找法找寻边界值

    之前的都是在数组中找到一个数要与目标相等,如果不存在则返回-1。我们也可以用二分查找法找寻边界值,也就是说在有序数组中找到“正好大于(小于)目标数”的那个数。

    用数学的表述方式就是:

         在集合中找到一个大于(小于)目标数t的数x,使得集合中的任意数要么大于(小于)等于x,要么小于(大于)等于t。

     

    举例来说:

    给予数组和目标数

    int array = {2, 3, 5, 7, 11, 13, 17};
    int target = 7;

    那么上界值应该是11,因为它“刚刚好”大于7;下届值则是5,因为它“刚刚好”小于7。

    用二分查找法找寻上届

    //Find the fisrt element, whose value is larger than target, in a sorted array 
    int BSearchUpperBound(int array[], int low, int high, int target)
    {
    //Array is empty or target is larger than any every element in array
    if(low > high || target >= array[high]) return -1;

    int mid = (low + high) / 2;
    while (high > low)
    {
    if (array[mid] > target)
    high = mid;
    else
    low = mid + 1;

    mid = (low + high) / 2;
    }

    return mid;
    }

    与精确查找不同之处在于,精确查找分成三类:大于小于等于(目标数)。而界限查找则分成了两类:大于不大于

    如果当前找到的数大于目标数时,它可能就是我们要找的数,所以需要保留这个索引,也因此if (array[mid] > target)时 high=mid; 而没有减1。

    用二分查找法找寻下届

    //Find the last element, whose value is less than target, in a sorted array 
    int BSearchLowerBound(int array[], int low, int high, int target)
    {
    //Array is empty or target is less than any every element in array
    if(high < low || target <= array[low]) return -1;

    int mid = (low + high + 1) / 2; //make mid lean to large side
    while (low < high)
    {
    if (array[mid] < target)
    low = mid;
    else
    high = mid - 1;

    mid = (low + high + 1) / 2;
    }

    return mid;
    }

    下届寻找基本与上届相同,需要注意的是在取中间索引时,使用了向上取整。若同之前一样使用向下取整,那么当low == high-1,而array[low] 又小于 target时就会形成死循环。因为low无法往上爬超过high。

     

    这两个实现都是找严格界限,也就是要大于或者小于。如果要找松散界限,也就是找到大于等于或者小于等于的值(即包含自身),只要对代码稍作修改就好了:

    去掉判断数组边界的等号:

    target >= array[high]改为 target > array[high]

    在与中间值的比较中加上等号:

    array[mid] > target改为array[mid] >= target

     

    用二分查找法找寻区域

    之前我们使用二分查找法时,都是基于数组中的元素各不相同。假如存在重复数据,而数组依然有序,那么我们还是可以用二分查找法判别目标数是否存在。不过,返回的index就只能是随机的重复数据中的某一个。

    此时,我们会希望知道有多少个目标数存在。或者说我们希望数组的区域。

    结合前面的界限查找,我们只要找到目标数的严格上届和严格下届,那么界限之间(不包括界限)的数据就是目标数的区域了。

     

    //return type: pair<int, int>
    //the fisrt value indicate the begining of range,
    //the second value indicate the end of range.
    //If target is not find, (-1,-1) will be returned
    pair<int, int> SearchRange(int A[], int n, int target)
    {
    pair<int, int> r(-1, -1);
    if (n <= 0) return r;

    int lower = BSearchLowerBound(A, 0, n-1, target);
    lower = lower + 1; //move to next element

    if(A[lower] == target)
    r.first = lower;
    else //target is not in the array
    return r;

    int upper = BSearchUpperBound(A, 0, n-1, target);
    upper = upper < 0? (n-1):(upper - 1); //move to previous element

    //since in previous search we had check whether the target is
    //in the array or not, we do not need to check it here again
    r.second = upper;

    return r;
    }

    它的时间复杂度是两次二分查找所用时间的和,也就是O(log n) + O(log n),最后还是O(log n)。

     

    在轮转后的有序数组上应用二分查找法

    之前我们说过二分法是要应用在有序的数组上,如果是无序的,那么比较和二分就没有意义了。

    不过还有一种特殊的数组上也同样可以应用,那就是“轮转后的有序数组(Rotated Sorted Array)”。它是有序数组,取期中某一个数为轴,将其之前的所有数都轮转到数组的末尾所得。比如{7, 11, 13, 17, 2, 3, 5}就是一个轮转后的有序数组。非严格意义上讲,有序数组也属于轮转后的有序数组——我们取首元素作为轴进行轮转。

    下边就是二分查找法在轮转后的有序数组上的实现(假设数组中不存在相同的元素)

     

    int SearchInRotatedSortedArray(int array[], int low, int high, int target) 
    {
    while(low <= high)
    {
    int mid = (low + high) / 2;
    if (target < array[mid])
    if (array[mid] < array[high])//the higher part is sorted
    high = mid - 1; //the target would only be in lower part
    else //the lower part is sorted
    if(target < array[low])//the target is less than all elements in low part
    low = mid + 1;
    else
    high = mid - 1;

    else if(array[mid] < target)
    if (array[low] < array[mid])// the lower part is sorted
    low = mid + 1; //the target would only be in higher part
    else //the higher part is sorted
    if (array[high] < target)//the target is larger than all elements in higher part
    high = mid - 1;
    else
    low = mid + 1;
    else //if(array[mid] == target)
    return mid;
    }

    return -1;
    }

    对比普通的二分查找法,为了确定目标数会落在二分后的那个部分,我们需要更多的判定条件。但是我们还是实现了O(log n)的目标。

     

    二分查找法的缺陷

    二分查找法的O(log n)让它成为十分高效的算法。不过它的缺陷却也是那么明显的。就在它的限定之上:

    必须有序,我们很难保证我们的数组都是有序的。当然可以在构建数组的时候进行排序,可是又落到了第二个瓶颈上:它必须是数组

    数组读取效率是O(1),可是它的插入和删除效率却是O(n2)。因而导致构建有序数组变成低效的事情。

     

    解决这些缺陷问题更好的方法应该是使用二叉查找树了,最好自然是自平衡二叉查找树了,自能高效的(O(log n))构建有序元素集合,又能如同二分查找法一样快速的搜寻目标数。

    展开全文
  • 编写程序对数据序列采用二查找法和顺序查找法查找元素的下标,要求使用类模板实现(其中二分法查找算法要求用递归实现,给定数据序列有序)。
  • 折半查找,也称二分查找,在某些情况下相比于顺序查找,使用折半查找算法的效率更高。但是该算法的使用的前提是静态查找表中的数据必须是有序的。 折半查找算法 静态查找表{5,13,19,21,37,56,64,75,80,88,92}采用...
  • 解决查找问题的一个基本解法是二分查找法 Binary Search 对于有序数列,才能使用二分查找法 如上图所示,首先找到数列的中间元素,如果等于要查找的元素,查找就停止, 如果不等于,判断是大于中间元素还是小于中间...
  • 数据结构方法之二分查找法

    万次阅读 2012-10-13 12:40:32
    一、什么是二分查找法?(略) 二、二分查找法的性能分析。 二分查找法的平均查找长度是ASL=log2(n+1)-1 (n>50) ★例题: 长度为12的有序表(a1,a2,...a12)(其中ai当i时),进行折半查找,在假 定查找不成功时,...
  • 分查找法又称为折半查找,适合已排序好的数据集合进行查找,时间复杂度为O(log2n) 思路 假设一个有序数据集合,找出其最中间的元素,以中间元素为界将集合划分为左右两个子集 将中间元素与目标元素进行比较,...
  • 分查找法

    2020-12-28 22:53:17
    分查找法(Binary Search)算法,也叫折半查找算法。二分查找针对的是一个有序的数据集合,查找思想有点类似于分治思想。每次都通过跟区间的中间元素对比,将带查找的区间缩小为之前的一半,直到找到要查找的元素...
  • 如果想要在有序数据中进行查找想要的数据,二分查找法就个好方法,它可以大大缩短了搜索时间,是一种常见的查找方法。二分查找很好写,却很难写,下面,小编就简单向大家介绍一下二分查找,并演示器使用代码。1、...
  • 上次,我们总结了在Python数据结构中排序算法的实现,这次我们来实现二分查找算法。 二分查找,顾名思义就是从有序列表中的中间取值与要查找数据匹配,再依靠递归的思想可以非常简单地实现二算法。代码如下def ...
  • 分查找法应用

    2020-01-09 11:21:45
    分查找法:在一组数据(数值)中查找某个值是否存在时,为优化效率采取将数据分段(以中间值为节点一分为二),在...二分查找法的概念请自行查找(百度上一堆),下面代码是个人在项目中分查找法的一个应用,...
  • 如果想要在有序数据中进行查找想要的数据,二分查找法就个好方法,它可以大大缩短了搜索时间,是一种常见的查找方法。二分查找很好写,却很难写,下面,小编就简单向大家介绍一下二分查找,并演示器使用代码。1、...
  • 上次刷LeetCode提到了二分查找法,但是最后没有用二分法实现,二分查找法是非常基础的算法,也比较容易掌握,这里二分法进行一些总结。 二分法一般要求这几点 1. 已经排好序应当没有重复值,当有重复值时,下面...
  • 例如,在{5,21,13,19,37,75,56,64,88 ,80,92}这个查找表使用折半查找算法查找数据之前,需要首先该表中的数据按照所查的关键字进行排序:{5,13,19,21,37,56,64,75,80,88,92}。 在折半查找之前查找表按...
  • 分查找法分析

    2021-01-28 10:55:51
    《Java数据结构与算法》中在分查找法做分析时,是以序数组是前提 有序数组 总所周知,在一系列面试题中都会有序数组的特点进行描述 查找快,增删慢 如下代码中,可以得到分析 插入数据时,会线性查询出...
  • 输入记录信息,使用起泡排序记录进行升序排序,并采用二分查找查找指定key的记录是否存在。 项目结构: 程序设计思路: 定义记录类型Record 定义查找排序类Zsort设计起泡排序和二分查找算法 初始化算法init()...
  • c语言:折半查找法(二分查找法

    千次阅读 2019-07-25 17:53:56
    折半查找法(half-interval search) ...注意:折半查找法仅适用于已有顺序的数组、数据进行操作!!! 例如:要在数组arr[]={8,7,9,6,4,1,2,5,3,10,11};中查找key=7的位置;首先,我们要先将数组arr中...
  • 如果想要在有序数据中进行查找想要的数据,二分查找法就个好方法,它可以大大缩短了搜索时间,是一种常见的查找方法。二分查找很好写,却很难写,下面,小编就简单向大家介绍一下二分查找,并演示器使用代码。 1、...
  • 如果想要在有序数据中进行查找想要的数据,二分查找法就个好方法,它可以大大缩短了搜索时间,是一种常见的查找方法。二分查找很好写,却很难写,下面,小编就简单向大家介绍一下二分查找,并演示器使用代码。1、...
  • 如果想要在有序数据中进行查找想要的数据,二分查找法就个好方法,它可以大大缩短了搜索时间,是一种常见的查找方法。二分查找很好写,却很难写,下面,小编就简单向大家介绍一下二分查找,并演示器使用代码。1、...
  • java二分查找法

    2020-05-08 22:59:35
    * 一个从小到大排序且不重复数据的数组,可用二分查找法找出目标值的下标, * 时间复杂度是o(logn),即log2n,比如数组长度n是16,则log2n等于4(2的4次方等于16),代表最多查找4次就能找到 */ public class ...
  • 八、二分查找法: 1、冒泡排序 冒泡排序算法的运作如下: 比较相邻的元素。如果第一个比第二个大(升序),就交换他们两个。 每一对相邻元素作同样的工作,从开始第一到结尾的最后一对。这步做完后,最后....
  • 排序算法效率 部分:冒泡排序 选择排序 插入排序 ...顺序查找某个数组按顺序比较找到数据分查找:重要前提,数组必须是一个有序数组(如果无序则必须先排好序) 示例代码: 必须是有序数组才能执行二分查找
  • 这里写自定义目录标题二分查找法原理代码实现注意事项(重要)注意1:注意2: 二分查找法原理 作用:二分查找法是快速查找有序数组A中某元素e的下标的方法。 原理:对查找区间[l,h)尽可能分为等长的两个区间[l,m)...
  • 对于有序数组使用2分法...有序数组使用2分法第一次即可跳过数组的一半不需要遍历因此效率大为提高,尤其大数组,体现更为明显. template <typename T> void 查找数据阶梯法(T 数组, int 序, int 查) { int...
  • 引入:二分法思想无处不在,...针对二分法查找数据必须是有序的。2.二分法查找依赖于顺序表结构,也就是数组。因为二分法需要随机访问元素,也就是O(1)的复杂度找到对象,所以需要内存连续。如果使用链表,那么...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 620
精华内容 248
关键字:

对分法查找数据