美文网首页
循环有序数组查找

循环有序数组查找

作者: HannahLi_9f1c | 来源:发表于2019-02-02 12:56 被阅读0次

循环有序数组查找

  • 题目:循环有序数组就是类似于56781234这样的数组。用logn复杂度查找一个元素,并返回其下标;如果不存在则返回-1.
  • 思路:有序数组容易想到二分查找。但是需要加一些细节判断。
  1. 第一种情况:mid值落在前半部分有序数组中,那么继续判断要查找的n是否落在start和mid中间有序数组部分:是,那么end=mid-1;否则start=mid+1,向后半部分区域查找
  2. 第二种情况:mid值落在后半部分有序数组,通过a[mid]>a[start]可以判断,继续判断n是否落在mid和end之间:是,那么start=mid+1,否则end=mid-1,向前寻找。
  • 要注意的是除了要判断a[mid]是否等于n之外,还要判断a[start]和a[end]。
    public static int binarySearch(int a[],int n) {
        if(a==null||a.length==0)
            return -1;
        int start=0,end=a.length-1;
        int mid=(start+end)/2;
        while(start<=end) {
            if(a[start]==n)
                return start;
            if(a[end]==n)
                return end;
            if(a[mid]==n)
                return mid;
            mid=(start+end)/2;
            if(a[start]<a[mid]) {
                if(a[start]<n&&a[mid]>n)
                    end=mid-1;
                else
                    start=mid+1;
            }else {
                if(a[mid]<n&&n<a[end])
                    start=mid+1;
                else
                    end=mid-1;
            }
            
        }
        return -1;
    }


相关文章

  • 循环有序数组查找

    循环有序数组查找 题目:循环有序数组就是类似于56781234这样的数组。用logn复杂度查找一个元素,并返回其下...

  • 循环数组的二分查找--Java实现

    与普通二分查找的不同: 以上的查找对象为循环数组,而普通二分查找的对象为有序的普通数组; 正因为是循环数组,取中进...

  • 算法 -- 二分查找

    二分查找有两种实现:通过递归或循环 二分查找的前提是先要保证数组有序 递归 循环 github 完整代码 -- b...

  • JavaScript#33:数组--(搜索旋转排序)Search

    分析一: 给定一个循环无重复有序数组,如12345 ->34512​,查找给定数值target在数组中的下标,如没...

  • 算法题

    行列都是有序的二维数组,查找k是否存在【查找法】 二维数组中的查找(行列分别有序数组的二分查找)【递归法】 快速排...

  • (八)二分/插值/斐波那契查找算法

    一 顺序查找 没什么好说的,就是依次查找。对数组是否有序没有要求 二 二分查找 前提:数组有序 2.1 思路 目标...

  • JS数组的二分查找算法

    用途:对有序数组进行查找。如:查找指定元素在数组中的下标

  • 33. Search in Rotated Sorted Arr

    循环有序数组中查找一个元素,例如 [4,5,6,7,0,1,2] 中查找0,要求复杂度 O(log(n)). 思路...

  • 二分查找及其扩展

    在有序数组中,二分查找是效率较高的查找算法。二分查找一般有递归和迭代 对有序数组查找指定数字在数组中出现的次数//...

  • 算法-二分查找

    对有序数组进行查找 一、非递归 二、递归查找

网友评论

      本文标题:循环有序数组查找

      本文链接:https://www.haomeiwen.com/subject/gtsssqtx.html