二分查找的相关算法题

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/51292440

最近笔试经常遇到二分查找的相关算法题

1)旋转数组中的最小数字

2)在旋转数组中查找某个数

2)排序数组中某个数的出现次数

转载请注明原博客地址:http://blog.csdn.net/gdutxiaoxu/article/details/51292440

下面我来一一总结

旋转数组的最小数字

题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1.

实现数组的旋转见左旋转字符串

和二分查找法一样,用两个指针分别指向数组的第一个元素和最后一个元素。

我们注意到旋转之后的数组实际上可以划分为两个排序的子数组,而且前面的子数组的元素都大于或者等于后面子数组的元素。我们还可以注意到最小的元素刚好是这两个子数组的分界线。我们试着用二元查找法的思路在寻找这个最小的元素。

首先我们用两个指针,分别指向数组的第一个元素和最后一个元素。按照题目旋转的规则,第一个元素应该是大于或者等于最后一个元素的(这其实不完全对,还有特例。后面再讨论特例)。

接着我们得到处在数组中间的元素。如果该中间元素位于前面的递增子数组,那么它应该大于或者等于第一个指针指向的元素。此时数组中最小的元素应该位于该中间 元素的后面。我们可以把第一指针指向该中间元素,这样可以缩小寻找的范围。同样,如果中间元素位于后面的递增子数组,那么它应该小于或者等于第二个指针指 向的元素。此时该数组中最小的元素应该位于该中间元素的前面。我们可以把第二个指针指向该中间元素,这样同样可以缩小寻找的范围。我们接着再用更新之后的 两个指针,去得到和比较新的中间元素,循环下去。

按 照上述的思路,我们的第一个指针总是指向前面递增数组的元素,而第二个指针总是指向后面递增数组的元素。最后第一个指针将指向前面子数组的最后一个元素, 而第二个指针会指向后面子数组的第一个元素。也就是它们最终会指向两个相邻的元素,而第二个指针指向的刚好是最小的元素。这就是循环结束的条件。

核心实现代码:

int Min(int *numbers , int length)
{
    if(numbers == NULL || length <= 0)
        return;
 
    int index1 = 0;
    int index2 = length - 1;
    int indexMid = index1;
    while(numbers[index1] >= numbers[index2])
    {
        if(index2 - index1 == 1)
        {
            indexMid = index2;
            break;
        }
 
        indexMid = (index1 + index2) / 2;
        //如果下标为index1、index2和indexMid指向的三个数字相等,则只能顺序查找
        if(numbers[index1] == numbers[index2] && numbers[indexMid] == numbers[index1])
            return MinInOrder(numbers , index1 , index2);
 
        if(numbers[indexMid] >= numbers[index1])
            index1 = indexMid;
        else if(numbers[indexMid] <= numbers[index2])
            index2 = indexMid;
    }
    return numbers[indexMid];
}
 
//顺序查找
int MinInOrder(int *numbers , int index1 , int index2)
{
    int result = numbers[index1];
    for(int i = index1 + 1 ; i <= index2 ; ++i)
    {
        if(result > numbers[i])
            result = numbers[i];
    }
    return result;
}

 注意:当两个指针指向的数字及他们中间的数字三者相同的时候,我们无法判断中间的数字是位于前面的字数组还是后面的子数组中,也就无法移动两个指针来缩小查找的范围。此时,我们不得不采用顺序查找的方法。

2 旋转数组中查找某个数字

要求

      给定一没有重复元素的旋转数组(它对应的原数组是有序的),求给定元素在旋转数组内的下标(不存在的返回-1)。

例如

有序数组为{0,1,2,4,5,6,7},它的一个旋转数组为{4,5,6,7,0,1,2}。

  • 元素6在旋转数组内,返回2
  • 元素3不在旋转数组内,返回-1

分析

      遍历一遍,可以轻松搞定,时间复杂度为O(n),因为是有序数组旋转得到,这样做肯定不是最优解。有序,本能反映用二分查找,举个例子看看特点

      可以看出中间位置两段起码有一个是有序的(不是左边,就是右边),那么就可以在有序的范围内使用二分查找;如果不再有序范围内,就到另一半去找。

参考代码

int search(int A[], int n, int target) {
        int beg = 0;
        int end = n - 1;
        while (beg <= end)
        {
            int mid = beg + (end - beg) / 2;
            if(A[mid] == target)
                return mid;
            if(A[beg]  <= A[mid])
            {
                if(A[beg] <= target && target < A[mid])
                    end = mid - 1;
                else 
                    beg = mid + 1;
            }
            else
            {
                if(A[mid] < target && target <= A[end])
                    beg = mid + 1;
                else
                    end = mid - 1;
            }
        }
        return -1;
    }

扩展

      上边的有求是没有重复的元素,现在稍微扩展下,可以有重复的元素,其他的要求不变。

思路

      大致思路与原来相同,这是需要比较A[beg] 与 A[mid]的关系

  • A[beg]  < A[mid] ————左边有序
  • A[beg]  > A[mid] ————右边有序
  • A[beg]  = A[mid] ————++beg
boolean search(int A[], int n, int target) {
        int beg = 0;
        int end = n - 1;
        while (beg <= end)
        {
            int mid = beg + (end - beg) / 2;
            if(A[mid] == target) 
                return true;
            if(A[beg] < A[mid])
            {
                if(A[beg] <= target && target < A[mid])
                    end = mid - 1;
                else
                    beg = mid + 1;
            }
            else 0if(A[beg] > A[mid])
            {
                if(A[mid] < target && target <= A[end])
                    beg = mid + 1;
                else
                    end = mid - 1;
            }
            else
                ++beg;
        }
        return false;
    }

3 数字在排序数组中的出现次数

//二分查找,二分查找key第一次出现的位置,二分查找最后一次出现的key

//返回两者相减+1或者找到第一次出现的位置,向后查找
int binarySearchFirstPos(int * iArr, int l, int h, int key)

{

    while(l <= h )

    {

        int mid  = (l + h) / 2;

        if(iArr[mid] < key)

            l = mid +1;

        elseif(iArr[mid] > key)

            h = mid - 1;

        else

        {

            if(mid == l || iArr[mid - 1] != key)

                return mid;

            else 

                h = mid - 1;

        }

    }

    return -1;

}

int binarySearchLastPos(int * iArr, int l, int h, int key)

{

    while(l <= h)

    {

        int mid = (l + h) / 2;

        if(iArr[mid] < key)

            l =  mid + 1;

        elseif(iArr[mid] > key)

            h = mid - 1;

        else

        {

            if(mid == h || iArr[mid + 1] != key)

                return mid;

            else

                l = mid + 1;

        }

    }

    return -1;

}

int numOfKey(int * iArr, int length, int key)

{

    int firstPos = binarySearchFirstPos(iArr, 0, length - 1, key);

    int lastPos = binarySearchLastPos(iArr, 0, length - 1, key);

    cout << firstPos << "\t" << lastPos << endl;;

    if(firstPos == -1)

        return0;

    elsereturn lastPos - firstPos + 1;

}

今天就写到这里了,睡觉了。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

【Java学习笔记之十】Java中循环语句foreach使用总结及foreach写法失效的问题

foreach语句使用总结 增强for(part1:part2){part3}; part2中是一个数组对象,或者是带有泛性的集合. part1定义了一...

2777
来自专栏ACM算法日常

leetcode 41| 缺失的第一个正数

难点分析:是不是和笔者一样,刚看完一遍题目都不知道它在问什么~经过多次揣摩之后,笔者终于懂了这道题目到底在问什么。其实它就是给定一个数组,然后看看数组中是否包含...

1892
来自专栏北京马哥教育

正则表达式基本语法

\将下一字符标记为特殊字符、文本、反向引用或八进制转义符。例如,“n”匹配字符“n”。“\n”匹配换行符。序列“\\”匹配“\”,“\(”匹配“(”。^匹...

3627
来自专栏一个会写诗的程序员的博客

《零基础 Java 开发 》 第五章 数组第五章 数组

数组是一个基础的数据结构,它用来存储一组相同类型的元素的集合。数组非常有用,例如Java提供的集合类ArrayList、HashMap等都是基于数组来实现的。

1313
来自专栏十月梦想

运算符

=就是简单给变量的赋值,+(-,*,/,%,.)=等同于左边加上(减去,乘上,除以,求余数,字符连接)右边赋值给昨天

703
来自专栏Golang语言社区

【Go 语言社区】Go语言运算符

运算符是一个符号,告诉编译器执行特定的数学或逻辑操作。 Go语言有丰富的内置运算符和运算符提供的以下几种类型: 算术运算符 关系运算符 逻辑运算符 位运算符 赋...

36216
来自专栏Golang语言社区

【Go 语言社区】Go语言数组

Go编程语言提供称为数组的数据结构,其可存储相同类型的元素的一个固定大小的连续集合。数组用于存储数据的集合,但它往往是更加有用认为数组作为相同类型的变量的集合。...

36015
来自专栏Golang语言社区

Python基本运算符

什么是操作符? 简单的回答可以使用表达式4 + 5等于9,在这里4和5被称为操作数,+被称为操符。 Python语言支持操作者有以下几种类型。 算术运算符 比较...

4647
来自专栏流媒体

C++多态

当类存在虚函数时,编译器会为该类维护一个表,这个表就是虚函数表(vtbl),里面存放了该类虚函数的函数指针。在构造类的时候增加一个虚表指针(vptr)指向对应的...

1163
来自专栏WindCoder

《简明 Python 教程》学习笔记-运算符与表达式

又两天没更新了,暂且同步两篇之前的笔记。运算符与表达式这一块感觉主要就是运算符与它们的用法以及优先级了。

1062

扫码关注云+社区

领取腾讯云代金券