【二分查找专题】剑指 Offer 53 – I. 在排序数组中查找-跟着帅地玩副业，开拓第二曲线PlayOffer

youngsir 普通 2024年12月21日上午10:41

打卡

class Solution {
public:
    int countTarget(vector<int>& scores, int target) {
        if(scores.size()==0) return 0;
        if(scores.size()==1){
            if(scores[0] == target){
                return 1;
            }else{
                return 0;
            }
        }
        int start = find(scores,target);
        int end = find(scores,target+1);
        return end-start;
    }
    int find(vector<int>& scores,int target){
         int l = 0,r = scores.size()-1;
        while(l <= r){
            int mid = ((r-l)/2)+l;
            if(scores[mid]<target){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        return l;
    }
};

0 赞同 0 条回复

陆狗陆狗普通 2024年12月10日下午11:06

解题思路
– 找出目标数字在数组中第一次出现时的firstIndex，在数组中最后一次出现时的finalIndex，出现次数=finalIndex-firstIndex+1
– 第一次出现时的firstIndex=index(最后一个<目标值 )+1
– 后一次出现时的finalIndex=index(第一个>目标值)-1
– 特别注意在外层需要判断边界值，数组为null，数组长度为0，target<数组的最小值，target>数组的最大值
【题解1】

class Solution {
    public int countTarget(int[] scores, int target) {
        if (scores == null || scores.length == 0) {
            return 0;
        }
        // target<数组的最小值，说明等于target不可能存在
        // target>数组的最大值，说明等于target不可能存在
        if (scores[0] > target || scores[scores.length - 1] < target) {
            return 0;
        }
        int firstIndex = firstIndex(scores, target);
        int finialIndex = finialIndex(scores, target);
        return finialIndex - firstIndex + 1;
    }

    public int firstIndex(int[] scores, int target) {
        // 第一个节点就是最开始的下标时
        if (scores[0] == target) {
            return 0;
        }
        // 一般情况，开始查找
        int l = 0;
        int h = scores.length - 1;
        while (l < h) {
            // 右偏移，防止出现l=mid的情况，导致程序死循环
            int mid = l + (h - l + 1) / 2;
            if (scores[mid] > target) {
                h = mid - 1;
            } else if (scores[mid] == target) {
                h = mid - 1;
            } else {
                l = mid;
            }
        }
        // 直接不考虑越界是因为在外层已经考虑过了
        return l + 1;
    }

    public int finialIndex(int[] scores, int target) {
        // 最后一个节点就是最后的下标时
        if (scores[scores.length - 1] == target) {
            return scores.length - 1;
        }
        // 一般情况，开始查找
        int l = 0;
        int h = scores.length - 1;
        while (l < h) {
            int mid = l + (h - l) / 2;
            if (scores[mid] > target) {
                h = mid;
            } else if (scores[mid] == target) {
                l = mid + 1;
            } else {
                l = mid + 1;
            }
        }
        // 直接不考虑越界是因为在外层已经考虑过了
        return h - 1;
    }
}

0 赞同 0 条回复

秋山丽奈普通 2024年12月10日下午8:21

思路：分别找到 target 和 target+1 的左侧

class Solution {
    public int countTarget(int[] scores, int target) {
        int len = scores.length;

        if(len < 1){
            return 0;
        }

        if(len == 1){
            if(scores[0] == target){
                return 1;
            }else{
                return 0;
            }
        }

        // 找到 第一个 小于 target的位置 
        int left = find(scores, target);

        // 找到 第一个 大于 target的位置 -> 小于 (target+1) 位置
        int right = find(scores, target+1);

        return right - left ;
    }

    int find(int[] nums, int target){
        int left = 0;
        int right = nums.length-1;

        int mid = left + (right - left) / 2;

        while(left <= right){
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }

            mid = left + (right - left) / 2;
        }

        return left;
    }
}

0 赞同 0 条回复

黑键〰普通 2024年12月10日下午3:40

/**
 * @param {number[]} scores
 * @param {number} target
 * @return {number}
 */
var countTarget = function (scores, target) {
    if (scores.length == 0) return 0
    let left = 0
    let right = scores.length - 1
    // 先找右边界
    while (left <= right) {
        let mid = left + Math.floor((right - left) / 2)
        if (scores[mid] <= target) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    // 拿到右边界下标
    let rside = left
    // 重置左右指针
    left = 0
    right = scores.length - 1
    // 查找左边界
    while (left <= right) {
        let mid = left + Math.floor((right - left) / 2)
        if (scores[mid] < target) {
            left = mid + 1
        } else {
            // 等于的时候移动右边指针往里缩
            right = mid - 1
        }
    }
    let lside = right
    return rside - lside - 1
};

思路：找左边界和找右边界，搜查两次，根据左右边界下标来计算

0 赞同 0 条回复

Renasc 普通 2024年12月9日下午10:20

时间复杂度O(logn)，空间复杂度O(1)

class Solution {
    public int countTarget(int[] scores, int target) {
        // 1. 搜索右边界 right
        int i = 0, j = scores.length - 1;
        while (i <= j) {
            int mid = (i+j) / 2;

            if (scores[mid] <= target) {
                i = mid + 1;
            } else {
                j = mid - 1;
            }
        }
        int right = i;
        // 若数组中没有target，则提前返回
        if (j >= 0 && scores[j] != target) return 0;


        // 2. 搜索左边界
        i = 0; j = scores.length - 1;
        while (i <= j) {
            int mid = (i+j) / 2;
            if (scores[mid] < target) {
                i = mid + 1;
            } else {
                j = mid - 1;
            }
        }
        int left = j;
        return right - left - 1;
    }
}

0 赞同 0 条回复

Kisara 普通 2024年12月6日下午10:51

二分查找，第一个等于target和最后一个等于target

class Solution {
    public int countTarget(int[] scores, int target) {
        int left=first(scores,target);
        int right=last(scores,target);
        if(left<0||right<0) return 0;

        return right-left+1;
    }
    //找到第一个等于target的下标
    public int first(int[] scores, int target){
        if(scores==null||scores.length<=0)
            return -1;

        int l=0;
        int r=scores.length-1;

        while(l=target){
                r=mid;
            }
        }
        if(scores[l]!=target)return -1;
        return l;
        }


    //找到最后一个等于target的下标
    public int last(int[] scores,int target){
        if(scores==null||scores.length<=0)
            return -1;

        int l=0;
        int r=scores.length-1;

        while(ltarget){
                r=mid-1;
            }else if(scores[mid]<=target)
                l=mid;
        }
        if(scores[l]!=target) return -1;
        return l;
    }
}

Ologn o1

0 赞同 0 条回复

晓宇普通 2024年12月6日下午6:52

class Solution {
public:
   // 最后第一个等于 tar
    int search_upper(vector<int>& scores, int target){
        int l = 0, r = scores.size() - 1,mid;
        if(target > scores[r]) return -1;//如果都不存在，则返回-1
        while(l < r){
            mid = (r - l + 1) / 2 + l;  // 整数除2向下取整， 所以 r 一定比mid小
            // [l,mid,r]
            if(scores[mid] > target){
                r = mid - 1;
            }else if(scores[mid] <span class="text-highlighted-inline" style="background-color: #fffd38;"> target){
                l = mid ;
            }else{
                l = mid;
            }
        }</span>

<pre><code>    if(scores[l] != target) return -1;
        return l;


}
// 第一个等于 tar
int search_lower(vector<int>& scores, int target){
    int l = 0, r = scores.size() - 1, mid;
    if(target < scores[l]) return -1;//如果都不存在，则返回-1
    while(l < r){
        mid = (r - l) / 2 + l;
        if(scores[mid] > target){ // [l,mid,r]
            r = mid;
        }else if(scores[mid] == target){
            r = mid;
        }else{
            l = mid + 1;  // scores[l] < target
        }
    }
    if( scores[l] != target) return -1;
    return l;

}

int countTarget(vector<int>& scores, int target) {
    if(scores.empty()) return 0;
    if(scores.size() == 1 && scores[0] == target) return 1;
    int l = search_lower(scores,target);
    int r = search_upper(scores,target);
    if(l == -1 || r == -1) return 0;
    return r - l + 1;
}
</code></pre>

};
// 时间复杂度: o(lg n)； 空间复杂度: o(1)

0 赞同 0 条回复

Aatorx 永久会员 2024年12月6日下午3:46

class Solution {
public:
    int countTarget(vector& scores, int target) {
        if(scores.empty()){
            return 0;
        }
        int l = findl(scores, target);
        int r = findr(scores, target);
        if (l == -1 && r == -1){
            return scores.size();
        }
        if (l == -1){
            return r;
        }
        if (r == -1){
            return scores.size() - l - 1;
        }
        return r - l - 1;
    }
    int findl(vector& v, int target) {
        int l = 0;
        int r = v.size() - 1;
        if (v[l] >= target) {
            return -1;
        }
        while (l < r) {
            int mid = (r - l + 1) / 2 + l;
            if (v[mid] >= target) {
                r = mid - 1;
            }
            else {
                l = mid;
            }
        }
        return l;
    }

    int findr(vector& scores, int target) {
        int l = 0;
        int r = scores.size() - 1;
        if (scores[r] <= target) {
            return -1;
        }
        while (l < r) {
            int mid = (r - l) / 2 + l;
            if (scores[mid] > target) {
                r = mid;
            }
            else {
                l = mid + 1;
            }
        }
        return l;
    }
};

先寻找第一个小于target的下标l，在寻找第一个大于target的下表r，结果为r-l-1。
时间复杂度O(logN)，空间复杂度O(1)。

0 赞同 0 条回复

jaron 普通 2024年12月6日上午8:01

先找最后一个小于等于target的，再找第一个大于等于target的

class Solution {
    public int countTarget(int[] scores, int target) {
        if (scores == null || scores.length == 0) {
            return 0;
        }
        int l = l(scores, target);
        int r = r(scores, target);
        if (l == -1 || r == -1) {
            return 0;
        }
        return r - l + 1;
    }

    public int l(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        int m = 0;
        int ans = -1;
        while (l <= r) {
            m = l + (r - l) / 2;
            if (target <= nums[m]) {
                ans = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        if (ans != -1 && nums[ans] != target)
            ans = -1;
        return ans;
    }

    public int r(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        int m = 0;
        int ans = -1;
        while (l <= r) {
            m = l + (r - l) / 2;
            if (target >= nums[m]) {
                ans = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        if (ans != -1 && nums[ans] != target)
            ans = -1;
        return ans;
    }
}

0 赞同 0 条回复

lQl 永久会员 2024年12月6日上午12:23

先找最后一个小于目标值的数的下标,再找第一个大于目标值的数的下标,相减即为目标值的个数

class Solution {
    public int countTarget(int[] scores, int target) {
        int l = 0;
        int r = scores.length - 1;
        int small = -1;

        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (scores[mid] < target) {
                small = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        l = 0;
        r = scores.length - 1;
        int big = scores.length;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (scores[mid] > target) {
                big = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        return big - small - 1;
    }
}

0 赞同 0 条回复

Xiang. 永久会员 2024年12月5日下午10:49

思路：找第一个target和最后一个target的下标，做差+1，或者找到一头然后遍历进行统计直到不相等为止。
class Solution {
    public int countTarget(int[] scores, int target) {
        if(scores.length==0||scores[0]>target||scores[scores.length-1]<target) return 0;
        int left=searchRangeFirst(scores,target);
        if(scores[left]!=target) return 0;
        int right=searchRangeLast(scores,target);
        if(scores[right]!=target) right=right-1;
        return right-left+1;
    }
    //当查找第一个大于等于target的元素的位置时，此时target为第一个红色的位置，返回right
    public int searchRangeFirst(int[] nums, int target){
        int left=-1;
        int right=nums.length;
        int mid=0;
        while(left+1!=right){
            mid=((right-left)/2)+left;   //防止越界
            if(nums[mid]<target) left=mid;
            else right=mid;  //合并了大于或等于两种情况。 
        }
        return right;
    }
//当查找最后一个等于target的元素的位置时，此时target为最后一个蓝色的位置，返回left
    public int searchRangeLast(int[] nums, int target){
            int left=-1;
            int right=nums.length;
            int mid=0;
            while(left+1!=right){
                mid=((right-left)/2)+left;   //防止越界
                if(nums[mid]<=target) left=mid;//合并了小于或等于两种情况。
                else  right=mid; 
            }
            return left;
        }
}
时间复杂度：O（logn）
空间复杂度：O（1）

0 赞同 0 条回复

月下足迹普通 2024年12月5日下午7:12

//找第一个target和最后一个target的下标，然后计算个数
public int countTarget(int[] scores, int target) {
if(scores.length 0) return 0;

    int left = 0;
    int right = scores.length-1;
    int index_left = -1;
    int index_right = -1;
    while(left <= right) {
        int mid = (left + right) / 2;
        if (scores[mid] >= target) {
            if (scores[mid] == target) {
                index_left = mid;
            }
            right = mid - 1;
        }else {
            left = mid + 1;
        }
    }
    if (index_left == -1) {
        return 0;
    }

    left = 0;
    right = scores.length-1;

    while(left <= right) {
        int mid = (left + right) / 2;
        if (scores[mid] <= target) {
            if (scores[mid] == target) {
                index_right = mid;
            }
            left = mid + 1;
        }else {
            right = mid - 1;
        }
    }

    return index_right - index_left + 1;
}

0 赞同 0 条回复

苯庸普通 2024年12月5日下午6:15

class Solution {
public int[] searchRange(int[] nums, int target) {
if(nums.length 0) return new int[]{-1, -1};
int l = left_bound(nums, target);
int r = right_bound(nums, target);
if(nums[l] != target){
return new int[]{-1, -1};
}
return new int[]{l, r};
}

// 找左，判断右
int left_bound(int[] nums, int target){
    int l = 0, r = nums.length-1;
    while(l < r){
        int m = (l + r) / 2;
        if(nums[m] >= target){
            r = m;
        }else{
            l = m + 1;
        }
    }
    return r;
}

// 找右，判断左
int right_bound(int[] nums, int target){
    int l = 0, r = nums.length-1;
    while(l < r){
        int m = (l + r + 1) / 2;
        if(nums[m] <= target){
            l = m;
        }else{
            r = m - 1;
        }
    }
    return r;
}

}
时间：O（lgn）
空间：O（1）

0 赞同 0 条回复

迢迢星野普通 2024年12月5日下午6:15

class Solution {
    /**
     * 某班级考试成绩按非严格递增顺序记录于整数数组 scores，请返回目标成绩 target 的出现次数。
     * 求出 target 的左右边界，做差即可
     * 
     * @param scores
     * @param target
     * @return
     */
    public int countTarget(int[] scores, int target) {
        int left = leftBound(scores, target);
        if (left == -1) {
            return 0;
        }
        int right = rightBound(scores, target);
        return right - left + 1;
    }

    private int leftBound(int[] scores, int target) {
        int l = 0, r = scores.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (scores[mid] < target) {
                l = mid + 1;
            } else if (scores[mid] > target) {
                r = mid - 1;
            } else {
                // 求的是左侧边界，收缩右侧边界
                r = mid - 1;
            }
        }

        // 越界判断
        if (l < 0 || l >= scores.length) {
            return -1;
        }
        // 此时的 l、r 分别指向的是 target 的左侧边界（存在的话，如果不存在，则是大于 target 的最小索引）、小于 target 的最大索引
        return scores[l] == target ? l : -1;
    }

    private int rightBound(int[] scores, int target) {
        int l = 0, r = scores.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (scores[mid] < target) {
                l = mid + 1;
            } else if (scores[mid] > target) {
                r = mid - 1;
            } else {
                // 求的是左侧边界，收缩右侧边界
                l = mid + 1;
            }
        }

        // 越界判断
        if (r < 0 || r >= scores.length) {
            return -1;
        }

        // 此时的 l、r 分别指向的是 大于 target 的最小索引、target 的右侧索引（存在的话；如果不存在的话，则是小于 target 的最大索引）
        return scores[r] == target ? r : -1;
    }
}

思路：二分查找找到 target 的左右边界，计算该区间的大小即可。
时间复杂度：O(logn)
空间复杂度：O(1)

0 赞同 0 条回复

【二分查找专题】剑指 Offer 53 – I. 在排序数组中查找

共以下 14 个回答

# 回答此问题取消回复

【二分查找专题】剑指 Offer 53 – I. 在排序数组中查找

共以下 14 个回答

# 回答此问题 取消回复

# 回答此问题取消回复