LeetCode二分查找题目

孙泽辉

发布于：2021年7月16日

字数：374字

时长：1分钟

次浏览

练习一下二分查找

《剑指 Offer》 53 - I. 在排序数组中查找数字 I 难度：Easy ｜ 简单

相关知识点：数组、二分查找

题目链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/

官方题解：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solution/

《剑指 Offer》 53 - I. 在排序数组中查找数字 I 【LeetCode 力扣官方题解】_哔哩哔哩_bilibili

// 统计一个数字在排序数组中出现的次数。

// 示例 1:

// 输入: nums = [5,7,7,8,8,10], target = 8
// 输出: 2
// 示例 2:

// 输入: nums = [5,7,7,8,8,10], target = 6
// 输出: 0

function getFirstIndex(nums: number[],target:number) {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        const mid: number = left + Math.floor((right - left) / 2)
        if(nums[mid]<target){
            // target太大了，往右走 [mid+1,right]
            left = mid + 1;
        }else{
            // target小了，往左 [left,mid]
            right = mid;
        }
        
    }
    if(nums[left] === target){
        return left;
    }
    return -1;
}


function getLastIndex(nums: number[],target:number) {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        const mid: number = left + Math.ceil((right - left) / 2)
        if(nums[mid]<target){
            // target太大了，往右走 [mid+1,right]
            left = mid + 1;
        }else if(nums[mid]===target){
            // target等于mid,还能往右 [mid+1,right]
            left = mid
        }
        else{
            // target小了，往左 [left,mid-1]
            right = mid-1;
        }
    }
    if(nums[left] === target){
        return left;
    }
    return -1;
}


function solution(nums: number[],target:number) {
    if (nums.length == 0) return 0;
    const firstIndex: number = getFirstIndex(nums,target);
    if (firstIndex === -1) return 0;
    const lastIndex: number = getLastIndex(nums,target);
    return lastIndex - firstIndex + 1
}



const r = solution([5,7,7,8,8,10],7)
console.log(r) // 2