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

桎梏普通 2023年9月16日下午3:04

class Solution {
    public int[] searchRange(int[] nums, int target) {
        //两次二分查找
        int left = firstTarget(nums, target);
        int right = lastTarget(nums, target);
        return new int[]{left, right};
    }

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

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

0 赞同 0 条回复

ppopp 普通 2023年8月30日下午10:52

class Solution {
private:
int lc;
int rc;

public:
int search(vector& nums, int target) {
int len = nums.size();
if(!len) return 0;
int left = 0;
int right = len;
//left
while(left < right){
int mid = left + (right – left)/2;
if(nums[mid] target){
right = mid;
}else if(nums[mid] > target){
right = mid;
}else if(nums[mid] < target){
left = mid + 1;
}
}
if(left > right && left > len – 1) return -1;
else lc = left;

    while(left < right){
        int mid = left + (right - left)/2;
        if(nums[mid] == target){
            left = mid + 1;
        }else if(nums[mid] > target){
            right = mid;
        }else if(nums[mid] < target){
            left = mid + 1;
        }
    }
    if(left > right && left > len - 1) return -1;
    else rc = left - 1;

    return rc - lc + 1;                                                                             
}

};//滴滴

0 赞同 0 条回复

hi 普通 2023年8月15日下午8:27

二分出目标数出现的第一个和最后一个位置
答案为两个位置之间数的个数

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

        l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = (l + r + 1) >> 1;
            if(nums[mid] <= target) l = mid;
            else r = mid - 1;
        }

        return r - left + 1;
    }
};

0 赞同 0 条回复

艺普通 2023年8月3日下午8:56

“`c++代码
class Solution {
public:
int search(vector& nums, int target) {
return upper_bound(nums.begin(), nums.end(), target)-lower_bound(nums.begin(), nums.end(), target);
}
};

0 赞同 0 条回复

波雅汉库克普通 2023年7月31日上午11:34

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
         if(nums.size()==0){
            return {-1,-1};
        }
        int left = 0;
        int right = nums.size()-1;
        int mid;
        bool found = false;
        while(left <= right){
            mid = left + (right-left)/2;
            if(nums[mid] == target){
                found = true;
                break;
            }
            else if(nums[mid] > target){
                right = mid-1;
            }
            else{
                left = mid+1;
            }
        }
        if(!found){
            return {-1,-1};
        }
        left = mid;
        right = mid;
        int count = 1;
        while(left >= 0){
            if(nums[left]!=target){
                break;
            }
            count++;
            left--;
        }
        while(right < nums.size()){
            if(nums[right]!=target){
                break;
            }
            count++;
            right++;
        }
        return {left+1,right-1};

    }
};

做的是34题，输出不一样而已
时间复杂度：O(logn)
空间复杂度：O(1)

0 赞同 0 条回复

CaCO3 永久会员 2023年7月31日上午10:29

”’java
class Solution {
public int search(int[] nums, int target) {
//找到第一个大于target的下标和最后一个小于target的下标
int r = upper(nums,target);
int l = lower(nums,target);
if(r -1 && l -1){
return nums.length;
}
if(l -1 && r != -1){
return r;
}
if(r -1 && l != -1){
return nums.length – l -1;
}
if(r – l <= 1){
return 0;
}
return r – l – 1;
}
public int upper(int[] arr,int target){
int l = 0;
int r = arr.length – 1;
if(r < 0 || arr[r] <= target){
return -1;
}
while(l < r){
int mid = (l + r)/2;
if(arr[mid] > target){
r = mid;
}else{
l = mid + 1;
}
}
return l;
}
//找到最后一个小于target的
public int lower(int[] arr,int target){
int l = 0;
int r = arr.length – 1;
if(r < 0 || arr[l] >= target){
return -1;
}
while(l < r){
int mid = (l + r + 1)/2;
if(arr[mid] < target){
l = mid;
}else{
r = mid -1;
}
}
return l;
}
}
”’

0 赞同 0 条回复

枫梓。普通 2023年7月27日下午3:26

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.size() == 0) return 0;
        int right = findequal(nums, target);
        int cnt = 0;
        while(right>-1 &&nums[right--] == target){
             cnt++;
        }
        return cnt;
    }
    int findequal(vector<int> arr, int target) {
        int lt = 0;
        int rt = arr.size() - 1;
        while(lt < rt) {
            int mid = (rt - lt + 1) / 2 + lt;
            if(arr[mid] <= target) {
                lt = mid;
            } else {
                rt = mid - 1;
            }
        }
        return lt;
    }
};

时间O(long)

0 赞同 0 条回复

北辰普通 2023年7月26日下午8:42

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
                if(n==0) return 0;
        //先找到该目标数，然后再统计
        int l=0,r=n-1;
        while(l<r) {
            int mid = l+(r-l)/2;
            if(nums[mid]<target) l=mid+1;
            else r=mid;
        }
        int cnt=0;
        while(l<n&&nums[l++]==target) {
            cnt++;
        }
        return cnt;
    }
}

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

0 赞同 0 条回复

今天你刷题了嘛普通 2023年7月25日下午11:33

class Solution {
    int count = 0;
    public int search(int[] nums, int target) {
        if(nums.length==0) return 0;
        // 二分查找
        int left = floor_lower(nums, target);
        int right = floor_upper(nums, target);

        if(left<0 || right <0) return 0;
        return right-left+1;
    }

    // 找到第一个等于/小于target的数
    // 没有等于，就小于
    public int floor_lower(int[] nums, int target){
        int left = 0;
        int right = nums.length-1;
        if(nums[left]>target) return -1;
        // 左闭右闭
        while(left<=right){
            int middile = (right-left)/2 + left;
            if(nums[middile]>target){
                right = middile-1;
            } else if(nums[middile]==target){
                // 等于的时候，仍然要往左找，看有没有更小的坐标
                right = middile-1;
            } else{
                left = middile + 1;
            }
        }
        return right+1;
    }

    // 找到最后一个等于target的数，或者第一个大于target的数
    public int floor_upper(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        if(nums[right]<target) return -1;
        while(left<=right){
            int middile = (right-left)/2 + left;
            if(nums[middile]>target){
                right = middile-1;
            } else if(nums[middile]==target){
                // 等于的时候，仍然要往右找，看有没有更大的坐标
                left = middile+1;
            } else{
                left = middile + 1;
            }
        }
        return left-1; 
    }
}

时间复杂度：O（logn）
空间复杂度：O（n）

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年7月25日下午8:59

代码

class Solution {
    public int search(int[] nums, int target) {
        int left = search1(nums, target);
        int right = search2(nums, target);
        if(left<0||right<0){
            return 0;
        }
        return right-left+1;

    }

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

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

}

0 赞同 0 条回复

CKX 普通 2023年7月25日下午5:37

func search(nums []int, target int) int {
    //第一个等于target的元素下标
    leftbound := func(nums []int, target int) int {
        left := 0
        right := len(nums) - 1
        for left <= right {
            mid := left + (right-left)/2
            //[left, mid, right]
            if nums[mid] == target {
                right = mid - 1
            } else if nums[mid] < target {
                left = mid + 1
            } else if nums[mid] > target {
                right = mid - 1
            }
        }
        if left < 0 || left >= len(nums) {
            return -1
        }
        if nums[left] == target {
            return left
        }
        return -1
    }
    rightbound := func(nums []int, target int) int {
        left := 0
        right := len(nums) - 1
        for left <= right {
            mid := left + (right-left)/2
            //[left, mid, right]
            if nums[mid] == target {
                left = mid + 1
            } else if nums[mid] < target {
                left = mid + 1
            } else if nums[mid] > target {
                right = mid - 1
            }
        }
        if right < 0 || right >= len(nums) {
            return -1
        }
        if nums[right] == target {
            return right
        }
        return -1
    }

    left := leftbound(nums, target)
    right := rightbound(nums, target)

    if left == -1 || right == -1 {
        return 0
    }

    return right - left + 1

}

0 赞同 0 条回复

NullPointerException 普通 2023年7月25日上午11:25

class Solution {
public int search(int[] nums, int target) {
//排好序的数组一般都是二分
//用二分找找了左右遍历
int left =0;
int result =0;
int right = nums.length-1;
if(nums.length0)
{
return 0;
}
int mid = 0;
while(left<=right)
{
mid=(left+right)/2;
if(nums[mid]target)
{
break;
}
if(nums[mid]>target)
{
right=mid – 1;
}else
{
left = mid + 1;
}
}
if(mid>=0&&mid<=nums.length-1&&nums[mid]target)
{
int zuo =mid -1;
int you = mid +1;
result = 1 ;
while(zuo>=0&&nums[zuo]target)
{
zuo–;
result++;
}
while(you<=nums.length-1&&nums[you]target)
{
you++;
result++;
}
}
return result;

}

0 赞同 0 条回复

Edenms-u 普通 2023年7月24日下午11:05

int search(int* nums, int numsSize, int target){
    if(!nums) return 0;
    int left = 0;
    int right = numsSize - 1;
    int num = 0;
    int mid = left + (right - left)/2;
    while(mid >= left && mid <= right){
        if(nums[mid] < target){
            left = mid + 1;
            mid = left + (right - left)/2;
        }else if(nums[mid] > target){
            right = mid - 1;
            mid = left + (right - left)/2;
        }else{
            int lmid = mid - 1;
            while(lmid >= left){
                if(nums[lmid] != target){
                    break;
                }else{
                    num++;
                    lmid--;
                }
            }
            while(mid <= right){
                if(nums[mid] != target){
                    break;
                }else{
                    num++;
                    mid++;
                }
            }
            return num;
        }
    }       
    return 0;
}

二分➕前后循环遍历

0 赞同 0 条回复

Marshan 普通 2023年7月24日下午8:09

暴力

class Solution {
public:
    int search(vector& nums, int target) {
        int res = 0;
        for(int i = 0;i < nums.size();++i){
            if(nums[i] == target){
                res++;
            }
        }
        return res;
    }
};
//二分
二分
```CPP
class Solution {
public:
    int search(vector& nums, int target) {
        int l = 0;
        int r = nums.size() - 1;
        if(r+1 == 0){
            return 0;
        }
        if(nums[r] < target){
            return 0;
        }
        if(nums[r] == target){
            int res;
            while((r >= 0) && (nums[r] == target)){
                res++;
                r--;
            }
            return res;
        }
        while(l < r){
            int mid = (r - l) / 2 + l;
            if(nums[mid] > target){
                r = mid;
            }
            else if(nums[mid] == target){
                l = mid + 1;
            }
            else{
                l = mid + 1;
            }
        }
        // cout<= 0) && (nums[l - 1] == target)){
            res++;
            l--;
        }
        return res;
    }
};
```

0 赞同 0 条回复

普通 2023年7月23日下午11:47

c++ 代码这样也能过
class Solution {
int t=0;
public:
int search(vector& nums, int target)
{
for(int i=0;i<nums.size();i++)
{
if(targetnums[i])
t++;
}
return t;
}
};

0 赞同 0 条回复

人生何处不青山普通 2023年7月23日下午11:07

模板题，背模板就完事了

function search(nums: number[], target: number): number {
    let l = 0, r = nums.length - 1;
    while (l < r) {
        let mid = (l + r) >>> 1;
        if (nums[mid] > target) {
            r = mid;
        } else if (nums[mid] === target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    if (nums[l] !== target) return 0;
    let tmp = l;
    r = nums.length - 1;
    while (l < r) {
        let mid = (l + r + 1) >>> 1;
        if (nums[mid] < target) {
            l = mid;
        } else if (nums[mid] === target) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return (l - tmp) + 1;
};

0 赞同 0 条回复

Mby 普通 2023年7月23日下午9:07

class Solution {
    public int search(int[] nums, int target) {
        //常见
        //1.寻找第一个大于等于target的数， 2寻找第一个等于target的数
        //3.寻找最后一个大于等于target的数， 4.寻找最后一个等于targte的数
        int left = search2(nums, target);
        int right = search4(nums, target);

        if(left < 0 || right < 0)return 0;;
        return right - left + 1;
    }

    //2.寻找第一个等于target的数的下标
    int search2(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;
    }
    //4.寻找最后一个等于target的数下标
    int search4 (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月23日下午3:00

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

        int leftBorder = getIndex(nums, target);//找target的左边界
        int rightBorder = getIndex(nums, target + 1);//找target+1的左边界
        if(nums[leftBorder] != target) return 0;
        return rightBorder - leftBorder;

    }

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

        while(l <= r){
            int mid = l + ((r - l) >> 1);

            if(target <= nums[mid]){
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }

        return l;
    }
}

0 赞同 0 条回复

Luminous 普通 2023年7月23日下午2:25

class Solution {
    public int search(int[] nums, int target) {
        if(nums==null||nums.length==0) return 0;
        int left=findLeft(nums,target);
        if(left==-1) return 0;
        int right=findRight(nums,target);
        return right-left+1;
    }
    //寻找target第一次出现位置
    int findLeft(int[]nums,int target){
        int l=0,r=nums.length-1;
        while(l<r){
            int mid=(r-l)/2+l;
            if(nums[mid]<target){
                l=mid+1;
            }else if(nums[mid]==target){
                r=mid;
            }else{
                r=mid-1;
            }
        }
        if(nums[l]==target) return l;
        return -1;
    }
    //寻找target第二次出现位置
     int findRight(int[]nums,int target){
        int l=0,r=nums.length-1;
        while(l<r){
            int mid=(r-l+1)/2+l;
            if(nums[mid]<target){ 
                l=mid+1;
            }else if(nums[mid]==target){
                l=mid;
            }else{
                r=mid-1;
            }
        }
        if(nums[l]==target) return l;
        return -1;
    }

}

0 赞同 0 条回复

#00456B 普通 2023年7月23日上午12:11

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = leftBound(nums, target);
        if(left == -1){
            return 0;
        }
        int right = rightBound(nums, target);
        return right - left + 1;
    }
    //找左边界
    int leftBound(vector<int>& nums, int target){
        int left = 0;
        int right = nums.size() - 1;
        while(left <= right){
            int mid = left + (right - left)/2;
            if(nums[mid] < target){
                left = mid + 1;
            }
            else{
                right = mid - 1;
            }
        }
        if(left >= nums.size() || nums[left] != target){
            return -1;
        }
        return left;
    }
    //找右边界
    int rightBound(vector<int>& nums, int target){
        int left = 0;
        int right = nums.size() - 1;
        while(left <= right){
            int mid = left + (right - left)/2;
            if(nums[mid] > target){
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        if(right < 0 || nums[right] != target){
            return -1;
        }
        return right;
    }
};

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月22日下午11:40

7.22
Day14：下面是代码

 

class Solution {
    public int search(int[] nums, int target) {
        return helper(nums, target) - helper(nums, target - 1);
    }
    public int helper(int[] nums, int target){
        int i = 0, j = nums.length - 1;
        while(i <= j){
            int m = (i + j) >> 1;
            if(nums[m] <= target) i = m + 1;
            else j = m - 1;
        }
        return i;
    }
}

0 赞同 0 条回复

June 普通 2023年7月22日下午6:35

func search(nums []int, target int) int {
    if len(nums) == 0 || nums[len(nums)-1] < target || nums[0] > target{
        return 0
    }

    //大于target的第一个元素下标
    upperIndex := binarySearch(nums,target,true)
    //小于target的最后一个元素的下标
    lowerIndex := binarySearch(nums,target,false) 
    if lowerIndex == 0  && nums[0] == target {
        lowerIndex = -1
    }
    if upperIndex == len(nums)-1  && nums[len(nums)-1] == target {
        upperIndex = len(nums)
    }
    return upperIndex - lowerIndex -1
}

func binarySearch(arr []int, target int , upper bool) int {
    var l int = 0
    var r int = len(arr) - 1

    for l < r {
        var mid int
        if upper == true {
            mid = (r-l)/2 + l
        }else {
            mid = (r-l+1)/2 + l
        }
        if arr[mid] > target && upper == true{
            r = mid
        }else if arr[mid] > target && upper == false {
            r = mid - 1
        }else if arr[mid] == target && upper == true {
            l = mid + 1
        }else if arr[mid] == target && upper == false {
            r = mid - 1
        }else if arr[mid] < target && upper == true {
            l = mid + 1
        }else if arr[mid] < target && upper == false {
            l = mid
        }
    }
    return l
}

0 赞同 0 条回复

AD钙奶普通 2023年7月22日下午6:03

两次二分，求左右边界，右边界 – 左边界 + 1即可

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        if(nums == null) return 0;
        while(l <= r) {
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid - 1;
            else l = mid + 1;
        }
        int leftIndex = l;
        l = 0; r = nums.length - 1;
        while(l <= r) {
            int mid = l + r >> 1;
            if(nums[mid] > target) r = mid - 1;
            else l = mid + 1;
        }
        int rightIndex = r;
        return rightIndex - leftIndex + 1;
    }
}

0 赞同 0 条回复

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

共以下 23 个回答

# 回答此问题取消回复

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

共以下 23 个回答

# 回答此问题 取消回复

# 回答此问题取消回复