九号球普通 2023年11月19日下午10:45

“`java
//第一个大于target的下标
class Solution {
public int countTarget(int[] scores, int target) {
if (scores == null || scores.length == 0) {
return 0;
}
int l = 0;
int r = scores.length – 1;
if (scores[r] < target) { return 0; } while (l < r) { int mid = (r + l)/2; if (scores[mid] > target) {
r = mid;
} else {
l = mid + 1;
}
}
int count = 0;
for (int j = l; j >= 0; j–) {
if (scores[j] < target) { break; } else if (scores[j] == target) { count++; } } return count; } }

0 赞同 0 条回复

招舟子普通 2023年8月31日上午10:25

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

    //第一个大于target下标
    while(l<=r){
        int mid =l+(r-l)/2;
        if(nums[mid]<=target){
            l=mid+1;
        }else{
            r= mid-1;
        }
    }
    int a=l;
    l=0;
    r=nums.length-1;
    //第一个小于target下标
    while(l<=r){
        int mid =l+(r-l+1)/2;
        if(nums[mid]<target){
            l=mid+1;
        }else {
            r= mid-1;
        }
    }
    int b= r;
    return a-b-1;
}

}
加油

0 赞同 0 条回复

jhfuture 普通 2023年8月18日下午10:25

“`java
自己写的，刚好是帅地说的第一种
class Solution {
//时间复杂度可能会蜕变为O(n)
public int search(int[] nums, int target) {
//使用二分法找到其，然后再增加
//1.先处理特殊情况
if(nums.length==0) return 0;
if(nums[0]>target||nums[nums.length-1]target){
r=middle-1;
}else if(nums[middle]=0&&nums[l-1]==target){
count++;
l–;
}
return count;
}

}

0 赞同 0 条回复

CV大神普通 2023年8月15日下午8:51

 public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int left = 0, right = nums.length - 1;
        int middle = -1;
        //查找第一个大于target的位置
        while (left <= right) {
            middle = left + (right - left) / 2;
            if (nums[middle] > target) {
                right = middle - 1;
            } else if (nums[middle] == target) {
                left = middle + 1;
            } else {
                left = middle + 1;
            }
        }
        int rightBound = left;
        if (right > 0 && nums[right] != target) {//数组内没有这个元素，提前返回
            return 0;
        }
        //查找最后一个小于target的位置
        right = nums.length-1;
        left = 0;
        while (left <= right) {
            middle = left + (right - left) / 2;
            if (nums[middle] > target) {
                right = middle - 1;
            } else if (nums[middle] == target) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }

        int count = rightBound - right - 1;

        return Math.max(count, 0);
    }

0 赞同 0 条回复

怀瑾永久会员 2023年7月18日上午1:45

“`C++
int search(vector& nums, int target) {
int count = 0;
int left = 0;
int right = nums.size() – 1;

// 使用二分查找找到目标数字的第一个和最后一个位置
while (left <= right) {
    int mid = left + (right - left) / 2;

    if (nums[mid] == target) {
        // 统计目标数字出现的次数
        count++;
        int leftIdx = mid - 1;
        int rightIdx = mid + 1;

        // 继续向两侧搜索相同的数字
        while (leftIdx >= 0 && nums[leftIdx] == target) {
            count++;
            leftIdx--;
        }
        while (rightIdx < nums.size() && nums[rightIdx] == target) {
            count++;
            rightIdx++;
        }
        break;
    } else if (nums[mid] < target) {
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}
return count;

}
}

“`

0 赞同 0 条回复

Sexypig. 普通 2023年7月14日上午1:28

实现了一个在有序数组中查找目标值的函数。
首先，定义了一个Solution类，其中包含了两个函数leftBound和rightBound，分别用于查找目标值的左边界和右边界。
在search函数中，首先判断数组是否为空，如果为空则直接返回0。
然后调用leftBound和rightBound函数分别找到目标值的左边界和右边界，并计算区间的长度。
如果右边界为-1，则表示目标值不存在，返回0；否则返回右边界减去左边界再加1的结果。

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.size() == 0) return 0;
        int left = leftBound(nums, target);
        int right = rightBound(nums, target);
        return right == -1 ? 0 : right - left + 1;
    }
    int leftBound(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > target) {
                r = mid - 1;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else if (nums[mid] == target) {
                r = mid - 1;
            }
        }
        if (l < 0 || l >= nums.size()) return -1;
        return nums[l] == target ? l : -1;
    }
    int rightBound(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > target) {
                r = mid - 1;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else if (nums[mid] == target) {
                l = mid + 1;
            }
        }
        if (r < 0 || r >= nums.size()) return -1;
        return nums[r] == target ? r : -1;
    }
};

int main() {
    // 创建一个 Solution 对象
    Solution solution;

    // 创建一个测试用例
    vector<int> nums = {1, 2, 2, 2, 2, 2, 4, 5};
    int target = 3;

    // 调用解决方案中的函数进行测试
    int result = solution.search(nums, target);

    // 输出结果
    cout << "结果: " << result << endl;

    return 0;
}

0 赞同 0 条回复

彦，，# 普通 2023年7月14日上午12:33

时间复杂度 O(log⁡n)

int binarySearch(vector<int>& nums, int target, bool lower) {
        int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    int search(vector<int>& nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) 
        {
            return rightIdx - leftIdx + 1;
        }
        return 0;
    }

0 赞同 0 条回复

BOZ 普通 2023年7月12日下午4:05

【思路】讲问题解构为“找到该元素的第一个下标”与“找到该元素的最后一个下标”
【复杂度】时间O(logn)，空间O(1)

class Solution {
public:
    int upper(vector<int>& nums, int target){
        // if not exist, return -1
        int len = nums.size();
        if (nums[len - 1] < target) return -1;

        int l = 0, r = len - 1;
        while (l < r) {
            int mid = (r - l) / 2 + l;
            // printf("l = %d, m = %d, r = %d\n", l, mid, r);
            if (nums[mid] <= target) l = mid + 1;
            else r = mid - 1;
        }
        if (nums[l] != target) {
            if (l && nums[l - 1] == target) return l - 1;
            else return -1;
        }
        return l;
    }

    int lower(vector<int>& nums, int target){
        // if not exist, return -1
        int len = nums.size();
        if (nums[0] > target) return -1;

        int l = 0, r = len - 1;
        while (l < r) {
            int mid = (r - l) / 2 + l;
            // printf("l = %d, m = %d, r = %d\n", l, mid, r);
            if (nums[mid] >= target) r = mid - 1;
            else { // nums[mid] < target
                if (l != mid) l = mid;
                else if (nums[r] <= target) l = r;
                else return l; 
            }
        }
        if (nums[l] != target) {
            if (l < len - 1 && nums[l + 1] == target) return l + 1;
            else return -1;
        }
        return l;
    }

    int search(vector<int>& nums, int target) {
        if (nums.empty()) return 0;
        int up = upper(nums, target);
        int low = lower(nums, target);
        // printf("up = %d, low = %d\n", up, low);
        if (up == -1) return 0;
        return (up - low + 1);
    }
};

【优化】还有优化的空间，可以把查找过程合并

0 赞同 0 条回复

江畅普通 2023年7月12日下午3:10

// 在排序数组中查找数字1
// 时间复杂度 O(logN)
// 空间复杂度 O(1)
class Solution {
private:

    // 出现 target 的左边界
    int leftBound(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;

        while(left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] < target) { left = mid + 1; }
            else { right = mid - 1; }
        }
        if (left >= nums.size() || nums[left] != target) { return -1; }
        return left;
    }

    // 出现 target 的右边界
    int rightBound(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;

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

        if (right < 0 || nums[right] != target) { return -1; }
        return right;
    }

public:
    int search(vector<int>& nums, int target) {
        int leftIdx = leftBound(nums, target);
        if (leftIdx == -1) { return 0; }
        int rightIdx = rightBound(nums, target);
        return rightIdx - leftIdx + 1;  
    }
};

0 赞同 0 条回复

憨憨永久会员 2023年7月12日下午1:02

看完模板后按着自己理解来的，可能有点繁琐

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        if(nums==null||nums.length<=0||nums[left]>target||nums[right]<target){
            return 0;
        }
        while(left<right){
            int mid=(right-left+1)/2+left;
            if(nums[mid]>target){
                right=mid-1;
            }else if(nums[mid]==target){
                right=mid-1;
            }else{
                left=mid;
            }
        }
        int ans=0;
        if(nums[left]==target){
            while(left<nums.length&&nums[left++]==target)ans++;
        }else{
            if(left+1<nums.length&&nums[left+1]==target)left++;
        }
        while(left<nums.length&&nums[left++]==target)ans++;

        return ans;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年7月11日上午9:54

java
class Solution {
    public int search(int[] nums, int target) {
        //先寻找第一个出现元素的下标，再往后寻找
        int cnt = 0;
        int l = 0;
        int r = nums.length - 1;
        if(l == r) { //判断只有一个元素的特殊情况
            if(nums[l] == target) {
                return 1;
            }
            return 0;
        }
        while(l < r) { //如果没有小于target的元素怎么办
            int mid = (r - l + 1)/2 + l;
            if(nums[mid] > target) {
                r = mid - 1;
            } else if(nums[mid] == target) {
                r = mid - 1;;
            } else { //nums[mid] < target
                l = mid;
            }
        }
        //找到第一个小于target的下标后，看一下后面的数有几个等于的
        if(l <= nums.length - 1 && nums[l] == target) {
            cnt ++; //[2,2,2] target=2的情况，没有小于target元素的处理
        }
        while(l + 1 <= nums.length - 1 && nums[++l] == target) {
            cnt ++;
        }
        return cnt;
    }
}

最坏情况下时间复杂度达到了O(n)

0 赞同 0 条回复

屠龙手段普通 2023年7月9日下午8:03

通过数组元素等于target时，让左右边界等于mid控制找到数组中第一个或最后一个target元素。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        left = self.upper(nums, target)
        right = self.lower(nums, target)
        if left == -1 or right == -1:
            return 0
        return right - left + 1

    def upper(self, nums, target):
        left = 0
        right = len(nums) - 1
        if nums[right] < target:
            return -1
        while left < right:
            mid = (right - left) // 2 + left
            if nums[mid] == target:
                right = mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left

    def lower(self, nums, target):
        left = 0
        right = len(nums) - 1
        if nums[left] > target:
            return -1
        while left < right:
            mid = (right - left + 1) // 2 + left
            if nums[mid] == target:
                left = mid
            elif nums[mid] < target:
                left = mid
            else:
                right = mid - 1
        return left

0 赞同 0 条回复

残月冷骄阳普通 2023年7月9日下午7:13

复杂度

时间复杂度: $O(nlogn)$
空间复杂度: $O(1)$

Code

class Solution {
    public int search(int[] nums, int target) {
        int greate = firstGreater(nums,target);
        int less = lastLess(nums,target);
        if(greate>=0 && less>=0){
            return greate-less+1;
        }
        return 0;

    }
    public static int firstGreater(int[] arr,int target){
        int left = 0;
        int right = arr.length - 1;
        if (right<0|| arr[right] < target) {
            return -1;
        }
        while (left < right) {
            //注意向上取余
            int mid = (right - left+1) / 2 + left;
            if (arr[mid] > target) {
                right = mid-1;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else if (arr[mid] == target) {
                left = mid;
            }
        }
        if (arr[left] == target) {
            return left;
        }
        return -1;
    }
    public static int lastLess(int[] arr,int target){
        int left = 0;
        int right = arr.length - 1;
        if (right<0 || arr[left] > target) {
            return -1;
        }
        while (left < right) {
            int mid = (right-left) / 2 +left;
            if (arr[mid] > target) {
                right = mid;
            } else if (arr[mid] < target) {
                left = mid+1;
            } else if (arr[mid] == target) {
                right = mid ;
            }
        }
        if (arr[left] == target) {
            return left;
        }
        return -1;
    }
}

0 赞同 0 条回复

Vow the vow。普通 2023年7月6日上午9:47

先用二分查找找到等于target的左边界，再向右遍历计算个数。

public int search(int[] nums, int target) {
        int bound = leftBound(nums,target);
        if(bound == -1) return 0;
        int res = 0;
        for(int i = bound; i < nums.length; i++){
            if(nums[i] == target) res++;
            else if(nums[i] > target)  break;
        }
        return res;
    }

    public int leftBound(int[] num, int target){
        int l = 0, r = num.length-1;
        int bound = -1;
        while(l <= r){
            int mid = l + (r - l)/2;
            if(num[mid] > target){
                r = mid-1;
            }else if(num[mid] < target){
                l = mid + 1;
            }else{
                bound = mid;
                r = mid-1;
            }
        }
        return bound;
    }

0 赞同 0 条回复

局外人普通 2023年7月6日上午9:03

思路：使用二分查找模板，寻找target的两侧边界left与right，若存在则返回right-left+1即为出现次数，否则返回0
时间复杂度O(logn) 空间复杂度O(1)

class Solution {
    public int search(int[] nums, int target) {
        int left = leftBound(nums, target);
        if(left == -1)  return 0;
        int right = rightBound(nums, target);

        return right-left+1;
    }

    public int leftBound(int[] nums, int target){
        int low=0, high=nums.length-1;

        while(low<=high){
            int mid = low + (high-low)/2;
            if(nums[mid]<target){
                low = mid + 1;
            }else if(nums[mid]>target){
                high = mid - 1;
            }else if(nums[mid]==target){
                high = mid - 1;
            }
        }
        //low=high+1
        if(low>=nums.length || nums[low]!=target)   return -1;
        return low;
    }

    public int rightBound(int[] nums, int target){
        int low=0, high=nums.length-1;

        while(low<=high){
            int mid = low + (high-low)/2;
            if(nums[mid]<target){
                low = mid + 1;
            }else if(nums[mid]>target){
                high = mid - 1;
            }else if(nums[mid]==target){
                low = mid + 1;
            }
        }

        if(high<0 || nums[high]!=target)    return -1;
        return high;
    }
}

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月4日下午11:23

class Solution:

    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def floor_upper_bs(t):
            l, r = 0, len(nums) - 1
            if (nums[r] < t):
                return -1
            elif nums[r] == t:
                return r

            while l < r:
                m = (r - l) // 2 + l
                if (nums[m] > t):
                    r = m
                else:
                    l = m + 1

            if (l - 1 >= 0 and nums[l - 1] == t):
                return l - 1

            return l

        if not nums:
            return [-1, -1]

        left = floor_upper_bs(target - 1)

        if nums[left] != target:
            left = left + 1 if (left + 1 <= len(nums) - 1 and nums[left + 1] == target) else -1
        right = floor_upper_bs(target)
        print(right, nums[right])
        right = right if nums[right] == target else -1

        return [left, right]

返回了范围

0 赞同 0 条回复

Jerry 普通 2023年7月4日下午10:19

class Solution {
    public int search(int[] nums, int target) {
        int left_index = left_bound(nums, target);
        if (left_index == -1) {
            return 0;
        }
        int right_index = right_bound(nums, target);
        // 根据左右边界即可推导出元素出现的次数
        return right_index - left_index + 1;
    }

    int left_bound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        // 搜索区间为 [left, right]
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                // 搜索区间变为 [mid+1, right]
                left = mid + 1;
            } else if (nums[mid] > target) {
                // 搜索区间变为 [left, mid-1]
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 收缩右侧边界
                right = mid - 1;
            }
        }
        // 检查出界情况
        if (left >= nums.length || nums[left] != target) {
            return -1;
        }
        return left;
    }

    int right_bound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 这里改成收缩左侧边界即可
                left = mid + 1;
            }
        }
        // 这里改为检查 right 越界的情况，见下图
        if (right < 0 || nums[right] != target) {
            return -1;
        }
        return right;
    }
}

0 赞同 0 条回复

名字什么的好麻烦普通 2023年7月4日下午9:16

二分查找

class Solution {
    public int search(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(target<nums[mid])
                right=mid-1;
            else
                left=mid+1;
        }
        int j=left;
        if(right>=0&&nums[right]!=target)
            return 0;
        left=0;
        right=nums.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(target>nums[mid])
                left=mid+1;
            else
                right=mid-1;
        }
        int i=left;
        return j-i;
    }
}

0 赞同 0 条回复

yxy 普通 2023年7月4日下午8:25

时间复杂度O(logn)

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty()) return 0;
        int n=nums.size();
        int l=0,r=n-1;
        int left=0,right=0;
        while(l<r)
        {
            int mid=l+r>>1;
            if(nums[mid]>=target)
                r=mid;
            else
                l=mid+1;
        }
        if(nums[l]!=target)
            return 0;
        else
            left=l;
        l=0,r=n-1;
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(nums[mid]<=target)
                l=mid;
            else
                r=mid-1;
        }
        return l-left+1;
    }
};

0 赞同 0 条回复

行动派小彩笔普通 2023年7月4日上午12:38

class Solution {
public:
    // 寻找最后一个target
    int upper(vector<int>& nums,int target)
    {
        int left = 0;
        int right = nums.size()-1;
        if(nums.size()==0) return -1;
        while(left<right)
        {
            int mid = (right-left+1)/2+left; //为什么一定要向上取整
            if(nums[mid]>target)
            {
                right = mid-1;
            }
            else
            {
                left = mid+1;
            }
        }
        if(nums[left]!=target) return -1;
        return left;
    }
    // 寻找第一个target
    int lowr(vector<int>& nums,int target)
    {
        int left = 0;
        int right = nums.size()-1;
        if(nums.size()==0) return -1;
        while(left<right)
        {
            int mid = (right-left)/2+left;
            if(nums[mid]>=target)
            {
                right = mid;
            }
            else //nums[mid]<target
            {
                left = mid+1;
            }
        }
        if(nums[left]!=target) return -1;
        return left;
    }
    int search(vector<int>& nums, int target) {

        int left = lowr(nums,target);
        int right= upper(nums,target);
        if(left<0||right<0) return 0;
        return right-left+1;

    }
};

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月3日下午10:55

//思路：找到最左边和最右边的下标，作差+1
//注意判断没找到的情况
//时间O(logn) 空间O(1)
public int search(int[] nums, int target) {
        int leftIndex = searchLeft(nums,target);
        int rightIndex = searchRight(nums,target);

        if(leftIndex > nums.length - 1 || nums[leftIndex] != target){
            //没找到
            return 0 ;
        }

        return rightIndex - leftIndex + 1;
    }

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

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

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

        return left;
    }

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

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

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

        return right;
    }

0 赞同 0 条回复

小吕普通 2023年7月3日下午10:14

c++实现
int search(vector& nums, int target) {
if(nums.empty()) return 0;

    int l = 0, r = nums.size() - 1; //二分范围
    while( l < r)                   //查找元素的开始位置
    {
        int mid = (l + r )/2;
        if(nums[mid] >= target) r = mid;
        else l = mid + 1;
    }
    if( nums[r] != target) return 0;  //查找失败
    int begin = r;
    l = 0, r = nums.size() - 1;     //二分范围
    while( l < r)                   //查找元素的结束位置
    {
        int mid = (l + r + 1)/2;
        if(nums[mid] <= target ) l = mid;
        else r = mid - 1;
    }
    int end = r;
    return end - begin + 1;
}

0 赞同 0 条回复

伏月三十普通 2023年7月3日下午10:08

class Solution {
    public int search(int[] nums, int target) {
        if(nums==null || nums.length<=0){
            return 0;
        }

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

        int count=0;
        while(left<nums.length && nums[left]==target){  //满足这个条件循环
            count++;
            left++;
        }
        return count;
    }
}

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

0 赞同 0 条回复

张开怀普通 2023年7月3日下午10:06

class Solution{
public:
       int search(vector<int>& nums, int target){
              // 寻找第一个大于等于target的数的下标
              auto search1 = [&](vector<int>& nums, int target) -> int{
                     if(nums.empty()){
                            return -1;
                     }

                     int left = 0, right = nums.size()-1;
                     while(left<right){
                            int mid = left + (right - left) / 2;
                            if(nums[mid] < target){
                                   left = mid+1;
                            }else{
                                   right = mid;
                            }
                     }
                     return left;
              };

              // 寻找最后一个大于等于 target的数的下标
              auto search = [&](vector<int>& nums, int target) -> int{
                     if(nums.empty()){
                            return -1;
                     }

                     int left = 0, right = nums.size() - 1;
                     while(left<right){
                            int mid = left + (right - left + 1)/2;

                            if(nums[mid] > target){
                                   right = mid - 1;
                            }else{
                                   left = mid;
                            }
                     }
                     return left;
              };
              int left = search1(nums,target);
              int right = search2(nums,target);
              if(left == -1 || right == -1 || nums[left] != target || nums[right] != target){
                     return 0;
              }
              return right - left +1 ;
       }
}

时间复杂度：log(n)
空间复杂度：O(1)

0 赞同 0 条回复

张君雅小妹妹普通 2023年7月3日下午9:48

时间复杂度：O(logN)
空间复杂度：O(1)

class Solution {
    public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return 0;
        }

        int left = getLeft(nums, target);
        int right = getRight(nums, target);
        return left == -1 || right == -1 ? 0 : right - left + 1;

    }

    // 寻找第一个等于target数的下标
    public int getLeft(int[] nums, int target){
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            if(nums[mid] > target){
                r = mid;
            } else if (nums[mid] == target){
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        return nums[l] == target ? l : -1;

    }

    // 寻找最后一个等于target的下标
    public int getRight(int[] nums, int target){
        int l = 0, r = nums.length - 1;
        while(l < r){
            int mid  = l + ((r - l + 1) >> 1);
            if(nums[mid] > target){
                r = mid - 1;
            } else if (nums[mid] == target) {
                l = mid;
            } else {
                l = mid;
            }
        }
        return nums[l] == target ? l : -1;
    }

}

0 赞同 0 条回复

Ming 普通 2023年7月3日下午6:54

寻找第一个等于target的数，考虑往右边寻找，第一个就是了
寻找最后一个等于target的数，考虑往左边寻找，第一个就是了

class Solution {
    public int search(int[] nums, int target) {
        if(nums.length == 0) return 0;
        // 寻找第一个等于target的下标
        int left = leftIndex(nums, target);
        // 寻找最后一个等于target的下标
        int right = rightIndex(nums,target);
        if(left < 0 || right < 0) return 0;
        return right-left+1;
    }

    // 寻找第一个等于target的下标,在右边
    public int leftIndex(int[] nums, int target) {
        if(nums == null || nums.length <= 0){
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while(left < right) {
            int mid = (right - left) / 2 + left;
            if(nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        // 判断该数是否存在
        if(nums[left] != target) return -1;
        return left;
    }
    // 寻找最后一个等于target的下标，在左边
    public int rightIndex(int[] nums, int target){
        if(nums == null || nums.length <= 0){
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while(left < right) {
            int mid = (right - left+1) / 2 + left;
            if(nums[mid] <= target) {
               left = mid;
            } else {
                right = mid - 1;
            }
        }
        // 判断该数是否存在
        if(nums[left] != target) return -1;
        return left;
    }
}

0 赞同 0 条回复

花老爷普通 2023年7月3日下午5:56

结合帅地给的四个模板
时间：O(logn)
空间：O(1)

class Solution {
    public int search(int[] nums, int target) {
        int leftIdx = floor_lower(nums, target);
        int rightIdx = floor_upper(nums, target);
        if (leftIdx < 0 || rightIdx < 0) {
            return 0;
        }
        return rightIdx - leftIdx + 1;
    }

    private int floor_upper(int[] nums, int target) {
        if (nums == null || nums.length <= 0) {
            return -1;
        }
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (nums[mid] <= target) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        if (nums[l] != target) {
            return -1;
        }
        return l;
    }

    private int floor_lower(int[] nums, int target) {
        if (nums == null || nums.length <= 0) {
            return -1;
        }
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (nums[l] != target) {
            return -1;
        }
        return l;
    }
}

0 赞同 0 条回复

Dsjh 普通 2023年7月3日下午4:05

MY

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty()){
            return 0;
        }
        int l = -1,r = nums.size();
        while(l+1 != r){
            // 左区域 < tar,右区域 >= tar
            int mid = l+(r-l)/2;
            if(nums[mid]<target) l = mid;
            else r = mid;
        }
        // 不存在
        if(l == nums.size()-1 || nums[r] != target){
            return 0;
        }


        int temp = r;
        l = -1,r = nums.size();
        while(l+1 != r){
            // 左区域 <= tar,右区域 > tar
            int mid = l+(r-l)/2;
            if(nums[mid]<=target) l = mid;
            else r = mid;
        }
        return r-temp;
    }
};

0 赞同 0 条回复

Yodl. 普通 2023年7月3日下午2:20

//使用二分法查找第一个等于target的下标和最后一个等于target的下标
class Solution {
public:
    int search(vector<int>& nums, int target) {
        vector<int> v(2,-1);
        if(nums.empty()) return 0;
        int n=nums.size(),l=0,r=n-1;
        while(l<r){
            int m=(r+l)/2;
            if(nums[m]>=target) r=m;
            else l=m+1;
        }
        if(nums[l]!=target) return 0;
        v[0]=l;
        r=n;
        while(l<r){
            int m=(r+l)/2;
            if(nums[m]<=target) l=m+1;
            else r=m;
        }
        v[1]=l-1;
        return v[1]-v[0]+1;
    }
};
//时间复杂度O(nlogn),空间复杂度O(1)

0 赞同 0 条回复

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

共以下 29 个回答

复杂度

Code

MY

# 回答此问题取消回复

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

共以下 29 个回答

复杂度

Code

MY

# 回答此问题 取消回复

# 回答此问题取消回复