美文网首页
二分查找--双调查找

二分查找--双调查找

作者: 编程小王子AAA | 来源:发表于2020-08-10 07:53 被阅读0次

双调查找:
如果一个数组中的所有元素是先递增后递减的,则称这个数组为双调的。编写一个程序,给定一个含有N 个不同int 值的双调数组,判断它是否含有给定的整数。

private static int findNum(int[] N, int key) {
        int l = 0;
        int r = N.length - 1;
        int aims = 0;
        //找最大值
        while (l < r) {
            aims = l + ((r - l) >> 1);
            if (N[aims] > N[aims - 1] && N[aims] < N[aims + 1]) {
                l = aims;
            } else if (N[aims] < N[aims - 1] && N[aims] > N[aims + 1]) {
                r = aims;
            } else {
                break;
            }
        }
        //左边
        int left = 0;
        int right = aims;
        int mid;
        while (left <= right) {
            mid = left + ((right - left) >> 1);
            if (N[mid] > key) {
                right = mid - 1;
            } else if (N[mid] < key) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        //右边,大小反过来排列,和上面不一样
        left = aims;
        right = N.length - 1;
        while (left <= right) {
            mid = left + ((right - left) >> 1);
            if (N[mid] < key) {
                right = mid - 1;
            } else if (N[mid] > key) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

相关文章

  • python二分查找算法

    文章概述 二分查找法介绍 简单查找与二分查找对比 二分查找  二分查找算法主要思想:在有序列表中查找指定元素,先从...

  • 数据结构和算法--二分查找

    二分查找 二分查找的思想 二分查找(Binary Search)算法,也叫折半查找算法。 二分查找针对的是一个有序...

  • 二分查找

    什么是二分查找?二分查找,也叫折半查找(Binary Search),它是一种效率较高的查找方法。二分查找的条件:...

  • 二分查找--双调查找

    双调查找:如果一个数组中的所有元素是先递增后递减的,则称这个数组为双调的。编写一个程序,给定一个含有N 个不同in...

  • 可查找重复元素的二分查找算法

    可查找重复元素的二分查找算法 二分查找算法思想:又称为 折半查找,二分查找适合对已经排序好的数据集合进行查找。假设...

  • day13

    查找算法 顺序查找 二分查找 差值查找 斐波那契查找 二分查找 前提数组必须是有序的。 升级 Interpolat...

  • 二分查找的循环写法与递归写法

    二分查找 二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但二分查找要求线性表必须...

  • 二分查找

    [TOC] 二分查找的基础模板 二分查找靠左的Index基础模板 二分查找靠右的Index基础模板 二分查找插入t...

  • 二分查找法

    二分查找法 二分查找法(递归)

  • 二分查找(递归、非递归)

    二分查找(递归) 二分查找(非递归)

网友评论

      本文标题:二分查找--双调查找

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