二分查找__牛客网

闷声发大财的牛客用户

class Solution {
public:
    /**
     * 二分查找
     * @param n int整型 数组长度
     * @param v int整型 查找值
     * @param a int整型vector 有序数组
     * @return int整型
     */
    int upper_bound_(int n, int v, vector<int>& a) {
        // write code here
        if(a[n-1]<v) return n+1;
        int left=0,right = n-1;
        int temp;
        while(left<right){
            int mid = (right+left)/2;
            if(a[mid]<v) {
                left = mid+1;
            }
            else if(a[mid]>=v){
                temp = mid;
                right = mid;
            }
        }
        return temp+1;
    }
};

发表于 2020-08-27 23:07:40 回复(8)

仿生佛能度电子鬼吗

菜鸡的代码

    public int upper_bound_ (int n, int v, int[] a) {
        // write code here
        int left=0,right=n-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(a[mid]<v){
                left=mid+1;
            }else if(a[mid]>=v){
                //如果数组中的第一个元素就大于目标值，那就直接加1返回
                if(mid==0) return mid+1;
                //判断一下是否为第一个大于等于的位置，利用了数组是有序的条件
                if(a[mid-1]>=v) {right=mid-1;}
                else return  mid+1;
            }
        }
        return n+1;
    }

发表于 2020-12-22 23:01:18 回复(1)

Java

执子一白

二分查找比较基础的思想
实际上手有几个需要注意的地方
1.确定循环跳出条件（可能有些情况需要特殊处理一下）
2.确定中间位置计算公式我这边使用的
findPos=startPos+((endPos-startPos) >> 1);
使用位运算是在考虑可以加快一点速度

import java.util.*;


public class Solution {
    /**
     * 二分查找
     * @param n int整型 数组长度
     * @param v int整型 查找值
     * @param a int整型一维数组 有序数组
     * @return int整型
     */
    public int upper_bound_ (int n, int v, int[] a) {
        // write code here
        //开始位置
        int startPos=0;
        //结束位置
        int endPos=n-1;
        //当前查找位置
        int findPos=(n-1) >> 1;
        //
        int firstAbove=-1;

        while(startPos<endPos){
            if(startPos>=endPos-1){
                if(a[startPos]==v){
                    firstAbove=startPos; 
                }
                if(a[endPos]==v){
                    firstAbove=endPos; 
                }
                break;
            }
            if(a[findPos]>v){
                endPos=findPos;
                findPos=startPos+((endPos-startPos) >> 1);
                //记录大于查找值节点，便于未找到相等节点时遍历返回
                firstAbove=findPos;
            }else if(a[findPos]<v){
                startPos=findPos;
                findPos=startPos+((endPos-startPos) >> 1);
            }else{
                //发现相等，跳出
                firstAbove=findPos;
                break;
            }
        }

        if(firstAbove==-1){
            return n+1;
        }
        int i=firstAbove;
        for(;i>=0;i--){
            if(a[i]<v){
               break;
            }
        }

       return i+2;



    }
}

发表于 2020-11-24 12:13:36 回复(0)

Java

牛客972939779号

**，他这是找第一个大于目标的数不是找第一个相等的数

2，1 ，{2，3，5}

输出数组仲第一个比1 大的数应该是 2 然后从1开始计算所以是 2在数组中的下标 0+1=1；

如果是找第一相等的数才是数组长度 3+1=4 那个测试用例 100，1 那个不过就是这个原因

题目实属坑，考阅读理解

发表于 2020-12-31 11:26:16 回复(0)

Java

牛客玩家001号

import java.util.Scanner;

public class Main {
    private static final String SPLIT_SYMBOL = "\\[";
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] firstPart = line.split(SPLIT_SYMBOL)[0].split(",");
        String[] secondPart = line.split(SPLIT_SYMBOL)[1].split("\\]")[0].split(",");
        int originArrLength = Integer.parseInt(firstPart[0]);
        int toFindNum = Integer.parseInt(firstPart[1]);

        int[] baseArr = new int[originArrLength];
        for (int i = 0; i < secondPart.length; i++) {
            baseArr[i] = Integer.parseInt(secondPart[i]);
        }

        System.out.print(findPosition(originArrLength, toFindNum, baseArr));
    }

    private static int findPosition(int originArrLength, int toFindNum, int[] baseArr) {
        int arrLength = baseArr.length;
        if (toFindNum > baseArr[arrLength - 1]) {
            return originArrLength + 1;
        }
        if (toFindNum <= baseArr[0]) {
            return 1;
        }
        // 正常二分逻辑
        return method(toFindNum, baseArr, arrLength);
    }
    private static int method(int toFindNum, int[] baseArr, int arrLength) {
        int tempNum = baseArr[arrLength / 2];
        int topSide = arrLength;
        int bottomSide = 0;
        int currentUseNum = arrLength / 2;
        while(toFindNum != tempNum) {
            if (toFindNum < tempNum) {
                currentUseNum = (bottomSide + currentUseNum) / 2;
                tempNum = baseArr[currentUseNum];
                topSide = currentUseNum;
                continue;
            }
            currentUseNum = (topSide + currentUseNum) / 2;
            tempNum = baseArr[currentUseNum];
            bottomSide = currentUseNum;
        }
        int findFirstTestNum = currentUseNum;
        if (toFindNum == tempNum) {
            while (findFirstTestNum > 0) {
                if (baseArr[--findFirstTestNum] == toFindNum) {
                    continue;
                }
                break;
            }
            return findFirstTestNum + 2;
        }
        return arrLength + 1;
    }
}

、、我搞不懂为什么提交的时候说我没有实际输出，只有用例输出96，但是我用他的“数据自测”功能输出结果也是96，本地idea也没问题。有大神帮看看吗

编辑于 2020-12-19 21:47:48 回复(0)

cqu后起之秀

class Solution {
public:
    /**
     * 二分查找
     * @param n int整型 数组长度
     * @param v int整型 查找值
     * @param a int整型vector 有序数组
     * @return int整型
     */
    int upper_bound_(int n, int v, vector<int>& a) {
        // write code here
        int l = 0, r = n - 1, mid;
        while (l <= r) {
            mid = (l + r) / 2;
            if (a[mid] == v) {
                while (a[mid] == a[mid-1]) {//找到v输出第一个等于v的值的下标+1 因为题目说明从1开始
                    mid--;
                }
                return mid + 1;
            }
            if (a[mid] > v) r = mid - 1;
            if (a[mid] < v) l = mid + 1;
        }
        for (int i = 0; i < n; i++) {//程序到此 说明a里面没找到等于v的值 输出第一个大于v的值的下标+1
            if (a[i] >= v) {
                return i+1;
            }
        }
        return n + 1;//a里面没有比v大的数 输出a的长度加1
    }
};

编辑于 2020-11-10 09:30:19 回复(0)

Java

tornado123

我只能说，题目怪怪的。

import java.util.*;


public class Solution {
    /**
     * 二分查找
     * @param n int整型 数组长度
     * @param v int整型 查找值
     * @param a int整型一维数组 有序数组
     * @return int整型
     */
    public int upper_bound_ (int n, int v, int[] a) {
        int i = 0, j = n-1;
        int mid;
        while(i <= j) {
            mid = (i + j) >>> 1;
            if (a[mid] == v) {
                //怕前面会有重复的数字出现，所以进行一次while，找出第一个该数的位置
                while(a[mid - 1] == v) {
                    mid--;
                }
                // 输出的位置从1开始，但是实际从0开始，所以要 + 1
                return mid + 1;
            }else if(a[mid] < v) {
                i =mid + 1;
            }else {
                j = mid -1;
            }
        }
        if(j < 0) {
            return 1;
        }else if(i >= n) {
            return n + 1;
        }else{
            // 此时 i < j
            if(a[j] > v){
                return j + 1;
            }else if(a[i] > v) {
                return i + 1;
            }
            return n + 1;
        }
    }
}

发表于 2020-10-28 11:33:15 回复(0)

Game7

//二分查找上边界查找改版
class Solution {
public:
    int upper_bound_(int n, int v, vector<int>& a) {
        int left=0,right=n-1;
        while(left<=right){
            int middle=left+(right-left)/2;
            if(a[middle]<v)        left=middle+1;
            else if(a[middle]>=v)   right=middle-1;
        }
        if(left==n)    return n+1;
        return left+1;
    }
};

发表于 2020-09-13 20:06:27 回复(0)

Python

qyzhizi

class Solution:
    def upper_bound_(self , n , v , a ):
        # write code here
        lo = 0
        hi = len(a)
        while lo < hi:
            mi = (lo + hi) // 2
            if a[mi] < v:
                lo = lo+1 # 这里写错了， 应该是 lo = mi + 1
            else:
                hi = mi
        return lo+1

清华邓公里面有这个二分查找思路：

区间[lo,hi) 表示待定区域，[0,lo),表示绝对小于value的区域， [mi,hi)，表示大于等于value的区域

最后得到的lo 的语意刚好满足，只不过本题给出的答案要加一，表示的不是秩，而是位置。

编辑于 2021-03-04 00:15:17 回复(4)

牛客966600716号

除了要用到二分法，这个题目所需要的其他情况条件也很多，如果你的二分法找到了值并不代表结束，你需要一直以这个位置往前找直到找到一个与其不相等的数才是最小下标；除此以外，还有需要判断不存在这个值的情况，比如题目给的{1,2,3,5,7}，而要你找6的时候，需要加一个额外分支条件：a[n-1]<6&&a[n]>6.这样才能通过100%的测试案例。

class Solution {
public:
    /**
     * 二分查找
     * @param n int整型 数组长度
     * @param v int整型 查找值
     * @param a int整型vector 有序数组
     * @return int整型
     */
    int upper_bound_(int n, int v, vector<int>& a) {
        // write code here
        if(n==0)
            return 1;
        else if(a[n-1]<v)
            return n+1;
        else if(v<a[0])
            return 1;
        else
        {
            int min=0;
            int max=n-1;
            while(min<=max)
            {
                int mid=(min+max)/2;
                if(a[mid]==v)
                {
                    while(a[mid]==a[mid-1])
                        mid=mid-1;
                    return mid+1;
                }
                else if(a[mid]<v && a[mid+1]>v)
                    return mid+2;
                else if(a[mid]>v)
                {
                    max=mid-1;
                }
                else
                    min=mid+1;
            }
            return n+1;
        }
    }
};

发表于 2020-09-10 20:27:24 回复(0)

流浪剑士

/**
 * 二分查找
 * @param n int整型 数组长度
 * @param v int整型 查找值
 * @param a int整型一维数组 有序数组
 * @param aLen int a数组长度
 * @return int整型
 */
int upper_bound_(int n, int v, int* a, int aLen ) {
    // write code here
    //给了2个数组长度应该都一样吧
    if(n <= 0)
    {
        return n+1;
    }
    //有序数组，判断一下降序还是升序，降序的话只需要比较第一个
    if(a[0] >= a[n-1])
    {
        if(a[0] < v)
        {
            return n+1;
        }
        else
        {
            return 1;
        }
    }
    //升序的话先比较一下最后一个
    if(a[n-1] < v)
    {
        return n+1;
    }
    //从左右分别开始查找，左起查找大于等于目标值的，右起查找小于目标值的
    int left = 0;
    int right = n-1;
    while(left < right)
    {
        if(a[left] >= v)
        {
            right = n;
            break;
        }
        left++;
        if(a[right] >= v)
        {
            right--;
        }
        else
        {
            right++;
            left = n;
            break;
        }
    }
    if(left < n )
    {
        return left + 1;
    }
    if(right < n)
    {
        return right + 1;
    }

    return n+1;
}

发表于 2020-08-26 17:11:33 回复(0)

菲尼克斯007

不知道出题人是懒还是语文没学好

发表于 2020-08-31 23:43:59 回复(21)

牛客219397578号

是我脑子有问题还是什么？

输入

5,4,[1,2,4,4,5]

输出

题目不是在数组中找第一个大于等于查找值的位置，那第一个4不就大于等于了，不应该输出第一个4的索引2吗？为什么输出3呢？

发表于 2020-08-27 15:29:22 回复(19)

C/C++

桃园饭桶

c++库里的 upper_bound 是第一个大于， lower_bound 是第一个大于等于，这里搞反了，其实是让你写lower_bound函数的功能。。。

int upper_bound_(int n, int v, vector<int> &a) {
    if (a.back() < v) return n+1;
    int l = 0, r = n, m = 0;
    while (l < r) {
        m = (l + r) >> 1;
        if (a[m] >= v) r = mid;
        else l = mid + 1;
    }
    return l + 1;
}

上面的语句 if (a[m] >= v) 改成大于，就是c++库里的 upper_bound 函数功能。

发表于 2020-08-26 11:02:10 回复(4)

.201908291501957

100,1,[2,3,4,4,4,7,7,8,10,10,11,12,13,14,15,15,17,18,19,23,24,24,24,24,25,26,26,26,27,27,28,29,29,30,33,36,38,38,40,40,41,43,43,43,44,46,46,47,51,52,52,53,54,56,57,57,57,58,58,61,61,61,62,64,64,66,66,67,67,67,70,72,74,74,74,75,75,78,78,78,79,79,80,83,83,83,83,84,84,86,88,89,89,90,91,91,92,93,93,96]

这个用例不是输出101？为什么测试用例写的输出应该为1？

发表于 2020-09-02 16:22:51 回复(16)

老实敦厚的某人

class Solution {
public:
    /**
     * 二分查找
     * @param n int整型 数组长度
     * @param v int整型 查找值
     * @param a int整型vector 有序数组
     * @return int整型
     */
    int upper_bound_(int n, int v, vector<int>& a) {
        // write code here
        int i = 0, j = n-1;
        while(i <= j) {
            int m_p = (i + j) / 2;
            int m_v = a[m_p];
            if(m_v == v) {
                if(m_p == 0 || a[m_p - 1] != v) {
                    return m_p + 1;
                } else {
                    j = m_p - 1;
                }
            } else if(m_v > v) {
                // 1 2 3 4 5
                if(m_p == 0 || a[m_p - 1] < v) {
                    return m_p + 1;
                }
                j = m_p - 1;
            } else if(m_v < v) {
                i = m_p + 1;
            }
        }
        return n+1;
    }
};

先写出普通的二分查找。然后修改两个地方：

1.当a[m] == v的时候，不能直接返回m，而是看一下m的左边有没有一样的数，如果有，那么右边界=m-1；如果没有，m就是那个数；

2.当a[m] > v的时候，看一下m左边那个数是不是小于v，如果是，直接返回m。

发表于 2020-09-02 13:00:52 回复(6)

Java

JaxonSuzy

首先判断有没有解，如果目标值小于数组最后一个数，那么一定有解。

改变二分查找，如果mid大于等于于目标值,可能我们的这个mid是最优的可能不是，左边还有，那么我们选择的范围就是【start，mid】,最后得到结果。

import java.util.*;
public class Solution {
    /**
     * 二分查找
     * @param n int整型 数组长度
     * @param v int整型 查找值
     * @param a int整型一维数组 有序数组
     * @return int整型
     */
    public int upper_bound_ (int n, int v, int[] a) {
        // write code here
        if(v>a[n-1]){
            return n+1;
        }
        int start = 0;
        int end = n-1;
        int mid=start+(end-start)/2;
        while(start < end){
            if(a[mid]>=v){
                end = mid;
            }else{
                start = mid+1;
            }
            mid = start+(end-start)/2;
        }
        return mid+1;
    }
}

编辑于 2020-10-26 12:23:14 回复(3)

dongmen

注意：
1.本题数组索引从1开始而非从零开始
2.本题目可转换为：查找元素v在有重复元素的有序数组array中的索引，若数组中不存在v，则返回其应该插入的第一个位置，插入之后数组仍保持有序。

理清以上两点之后，就可以套用二分查找的模板来解题了。

public class Solution {
    /**
     * 二分查找 
     * @param n int整型 数组长度
     * @param v int整型 查找值
     * @param a int整型一维数组 有序数组
     * @return int整型
     */
    public int upper_bound_ (int n, int v, int[] a) {

        int right = n - 1;
        int left = 0;
        int middle = 0;

        // 循环不变量： 
        // 若v能被找到，则保证v在[left, right]这个左闭右闭区间中
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // mid处的值和v相等，但是它可能并不是数组中第一个v
            // 因此继续缩小查找范围，排除掉重复的元素
            if (a[mid] >= v) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        // 循环结束时left > right
        // 分为2种情况：
        // 情况1：找到v，此时left指向v
        // 情况2：未找到v，此时left指向v应该被插入的位置
        // 因为该题索引从1开始，因此返回值要加1
        return left + 1;
    }
}

发表于 2020-10-15 13:47:17 回复(4)

Python

zawabest

# 二分查找
# @param n int整型 数组长度
# @param v int整型 查找值
# @param a int整型一维数组 有序数组
# @return int整型
#
class Solution:
    def upper_bound_(self , n , v , a ):
        # write code here
        l = 0
        r = n - 1
        while l <= r:
            m = (l + r) >> 1
            if a[m] >= v:
                r = m - 1
            else:
                l = m + 1
        return r + 2

发表于 2020-11-26 19:54:04 回复(0)

古德jio

各位兄弟，我这是理解错了题意了吗，不是找不到v就返回数组长度+1吗，还是我眼睛出问题了，找不到数组里面的1

用例输入：100,1,[2,3,4,4,4,7,7,8,10,10,11,12,13,14,15,15,17,18,19,23,24,24,24,24,25,26,26,26,27,27,28,29,29,30,33,36,38,38,40,40,41,43,43,43,44,46,46,47,51,52,52,53,54,56,57,57,57,58,58,61,61,61,62,64,64,66,66,67,67,67,70,72,74,74,74,75,75,78,78,78,79,79,80,83,83,83,83,84,84,86,88,89,89,90,91,91,92,93,93,96]
用例输出：1
实际输出：101

发表于 2020-09-25 15:28:52 回复(3)

二分查找

输入

输出

说明

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题