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

Gg 普通 2023年4月4日下午11:08

class Solution {
    public int search(int[] nums, int target) {
        if(nums.length == 0){
            return 0;
        }
        int last = findLast(nums,target);
        if(last == -1){
            return 0;
        }
        return findLast(nums,target) - findFirst(nums,target) + 1;
    }

    private int findFirst(int[] nums, int target){
        int i = 0;
        int j = nums.length;
        // 靠左指针逼近
        while(i < j){
            int mid = (j-i)/2 + i;
            if(nums[mid] < target){
                i = mid + 1;
            }else{
                j = mid;
            }
        }
        if(target == nums[i]){
            return i;
        }
        return -1;
    }

    private int findLast(int[] nums, int target){
        int i = 0;
        int j = nums.length - 1;
        // 靠右指针逼近
        while(i < j){
            int mid = (j-i+1)/2 + i;
            if(nums[mid] <= target){
                i = mid;
            }else{
                j = mid - 1;
            }
        }
        if(target == nums[i]){
            return i;
        }
        return -1;
    }
}

0 赞同 0 条回复

cute. 普通 2023年4月3日下午4:49

var search = function(nums, target) {
    var start = -1,
            end = -1,
            min = 0,
            max = nums.length - 1;
    //找出该数在左边第一次出现的位置
    while(min <= max){
        var mid = Math.floor((min + max)/2);
        if(target == nums[mid]){
            start = mid;   //记录下第一次出现的下标
            max = mid -1;//继续向前查找是否该数出现过
        }else if(target < nums[mid]){
            max = mid - 1;
        }else{
            min = mid + 1;
        }
    }
    //重置min 和max 的值，找出该数在右边最后一个出现的位置
    min = 0;
    max = nums.length - 1;
    while(min <= max){
        var mid = Math.floor((min + max)/2);
        if(target == nums[mid]){
            end = mid;
            min = mid + 1;
        }else if(target < nums[mid]){
            max = mid - 1;
        }else{
            min = mid + 1;
        }
    }
return start <= end && start !== -1 ? end - start + 1 : 0;
};

时间复杂度：O（logN)
空间复杂度：O（1）

0 赞同 0 条回复

宁永久会员 2023年1月14日上午11:27

class Solution {
    public int search(int[] nums, int target) {
        //常见题型：
        // 1.寻找第一个大于等于 target 的数   2.寻找第一个等于 target 的数
        // 3.寻找最后一个大于等于 target 的数 4.寻找最后一个等于 target 的数
        int left = search2(nums, target);
        int right = search4(nums, target);
        if(left < 0 || right < 0)
            return 0;
        return right - left + 1;
    }
    public int search2(int[] nums, int target){
        //2.寻找第一个等于 target 的数
        if (nums == null || nums.length == 0)
            return -1;
        int left = 0;
        int right = nums.length - 1;
        while(left < right){//退出循环的时候范围里面只有一个元素
            int mid = (right - left) / 2 + left;
            if(nums[mid] == target){
                right = mid;
            } else if(nums[mid] < target){
                left = mid + 1;
            } else{
                right = mid - 1;
            }
        }
        if(nums[left] == target){
            return left;
        }
        return -1;
    }
    public int search4(int[] nums, int target){
        //4.寻找最后一个等于 target 的数
        if (nums == null || nums.length == 0)
            return -1;
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int mid = (right - left + 1) / 2 + left;//需要向上取整防止死循环
            if(nums[mid] == target){
                left = mid;
            } else if(nums[mid] < target){
                left = mid + 1;
            } else{
                right = mid - 1;
            }
        }
        if(nums[right] == target){
            return right;
        }
        return -1; 
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月9日下午12:10

'''
思路：
基于二分查找的四个变形找出第一个的目标值和最后一个的目标值
需要注意的是最只有一个元素的数组的处理
'''


def search(nums, target):
    r = floor_upper(nums,target)
    # print("r",r)

    l = floor_lower(nums,target)
    # print("l",l)

    if r < 0 or l < 0:
        return 0
    else:
        return r - l + 1

def floor_lower(arr, target):
    l = 0
    r = len(arr) - 1

    if arr[l] > target:
        return -1

    if r == l and arr[l] == target:
        return 0

    if arr[l] == target:
        return l

    while l < r:
        #向上圆整
        mid = l + (r - l + 1) // 2
        if arr[mid] > target:
            r = mid - 1
        elif arr[mid] == target:
            r = mid - 1
        else:
            l = mid

    if l + 1 < len(arr) and arr[l + 1] == target:
        return l + 1

    return -1

0 赞同 0 条回复

lucca 普通 2023年1月7日下午4:07

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

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

0 赞同 0 条回复

浅夏的无奈普通 2022年11月30日下午11:05

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

    }
    //寻找第一个等于 target 的数的下标
    public int searchLeft(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 searchRight(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 条回复

🚲南下普通 2022年11月30日下午8:24

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int count = 0;
        for(auto c:nums){ //很简单，线性遍历
            if(c==target) count++;
        }
        return count;
    }
};

0 赞同 0 条回复

xye 普通 2022年11月23日下午2:17

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

//二分查找第一个等于tar的下标
func search1(nums []int, tar int) int {
    if nums == nil || len(nums) == 0 {
        return -1
    }
    l := 0
    r := len(nums) - 1
    for l < r {
        mid := l + (r - l) / 2
        if nums[mid] >= tar {
            r = mid
        }else{
            l = mid + 1
        }

    }
    if nums[l] != tar {
        return -1
    }
    return l
}

//二分查找最后一个等于tar的下标
func search2(nums []int, tar int) int {
    if nums == nil || len(nums) == 0 {
        return -1
    }
    l := 0
    r := len(nums) - 1
    for l < r {
        mid := l + (r - l + 1) / 2
        if nums[mid] <= tar {
            l = mid
        }else{
            r = mid - 1
        }

    }
    if nums[l] != tar {
        return -1
    }
    return l
}

时间O(logn) 空间O(1)

0 赞同 0 条回复

yanshuojune 普通 2022年11月19日下午12:32

解题思路：使用二分查找分别找出第一个等于target和最后一个等于target的元素，两个相减再加1即为结果
时间复杂度：O(logN)
空间复杂度：O(1)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 寻找第一个等于target和第一个大于target的下标-1，两下表的差值+1就是出现的次数
        # 寻找第一个等于target的元素下标
        def floor_lower(nums, target):
            L, R = 0, len(nums) - 1
            if not nums or nums[L] > target or nums[R] < target:
                return -1
            while L <= R:
                mid = L + (R - L) // 2
                if nums[mid] > target:
                    R = mid - 1
                elif nums[mid] < target:
                    L = mid + 1
                else:
                    R = mid - 1
            # 如果该元素不存在
            if nums[L] != target and L -1 >= 0:
                return -1
            return L

        # 寻找最后一个等于target 的元素下标
        def floor_upper(nums, taget):
            L, R = 0, len(nums) - 1
            if not nums or nums[R] < target or nums[L] > target:
                return -1
            while L <= R:
                mid  = L + (R - L) // 2
                if nums[mid] > target:
                    R = mid - 1
                elif nums[mid] < target:
                    L = mid + 1
                else:
                    L = mid + 1
            if nums[L - 1] == target and L - 1 >= 0:
                return L - 1
            return -1
        if floor_lower(nums, target) == -1:
            return 0
        else:
            return  floor_upper(nums, target) - floor_lower(nums, target) + 1

0 赞同 0 条回复

刺猬普通 2022年11月19日上午1:05

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.size() == 0 || target < nums.front() || target > nums.back())
            return 0;
        int l = -1;
        int r = nums.size() - 1;
        int k = 0;//计数
        while(l < r) {
            int mid = (r - l + 1)/2 + l;
            if(nums.at(mid) >= target){
                r = mid - 1;
            }else {
                l = mid;
            }
        }
        while( ++l < nums.size() && nums.at(l) == target) {
            k++;
        }
        return k;
    }
};

时间复杂度O(logn)

1 赞同 1 条回复

秊永久会员 @ 刺猬 2023年3月7日上午8:28

好思路👍🏻

登录以回复

黎昕普通 2022年11月12日下午10:59

二分，实际上是寻找大于target的最小数和小于target的最大数

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def helper(tar):    # 查找右边界的通用函数，应该记住
            i, j = 0, len(nums) - 1
            while i <= j:
                m = (i + j) // 2
                if nums[m] <= tar: i = m + 1
                else: j = m - 1
            return i
        return helper(target) - helper(target - 1)

0 赞同 0 条回复

Y7n05h 普通 2022年11月12日下午12:01

class Solution {
public:
    int search(vector<int>& nums, int target) {
        return upper_bound(begin(nums), end(nums), target) - lower_bound(begin(nums), end(nums), target);
    }
};

时间复杂度：O(lgN)
空间复杂度:O(1)

0 赞同 0 条回复

小肸永久会员 2022年11月11日下午9:29

思路：找到target的左右边界，来计算出个数。时间复杂度为O(logN)，空间复杂度O(1)。

class Solution {
    public int search(int[] nums, int target) {
        int leftIndex = getLeft(nums, target);
        int rightIndex = getRight(nums, target);
        return leftIndex == -1 || rightIndex == - 1 ? 0 : rightIndex - leftIndex + 1;
    }
    // 找到左边界,数组中第一个等于target的下标
    private int getLeft(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return -1;
        }
        int left = 0, right = len - 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的下标
    private int getRight(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return -1;
        }
        int left = 0, right = len - 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 条回复

@ 普通 2022年11月11日下午8:28

思路:找到第一个等于 target 的索引，然后从这个索引开始，分别向左和向右遍历，一旦不等于就终止
时间复杂度 O(logN）
**空间复杂度 O(1) **

class Solution {
    public int search(int[] nums, int target) {

        if (nums.length == 0)
            return 0;

        int l = 0, r = nums.length - 1, res = 0;

        while (l <= r) {
            int mid = l + (r - l) / 2;

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

        }

        int t = l;

        while (++l <= r) {
            if (nums[l] == target)
                res++;
            else
                break;
        }

        while (--t >= 0) {
            if (nums[t] == target)
                res++;
            else
                break;
        }


        return res;

    }

    public static void main(String[] args) {
        int[] ary = {1};
        Solution s = new Solution();
        int search = s.search(ary, 1);
        System.out.println(search);
    }
}

0 赞同 0 条回复

波波_1936 普通 2022年11月11日下午6:58

/**
     * 剑指 Offer 53 - I. 在排序数组中查找数字 I
     */
    public int search(int[] nums, int target) {
        //时间复杂度O(lgn)
        //空间复杂度O(1)
        int count = 0;
        if (nums == null || nums.length == 0) return count;
        if (nums[nums.length - 1] < target) return count;
        if (nums[0] > target) return count;

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

    }

0 赞同 0 条回复

lobort 普通 2022年11月9日下午7:21

class Solution {
    public int search(int[] nums, int target) {
            //方法一 循环遍历
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (target == nums[i]){
                count++;
            }
        }
        return count;

        //方法二  二分查找   时间复杂度O(logn)  空间复杂度O(1)
        int left = 0, right = nums.length - 1;
        int L = 0 , R = 0;

        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(nums[mid] <= target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        R = left ;   //找到左边界  
        if(right > 0 && nums[right] != target){
            return 0;
        }
        left = 0; right = nums.length - 1;
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        L = right;
        return R - L - 1; 
    }
}

0 赞同 0 条回复

Whatever 永久会员 2022年11月9日下午5:09

分别找到左右边界，最后进行运算得出元素个数。时间O(logn)，空间O(1)

class Solution {
    public int search(int[] nums, int target) {
        int left = leftBound(nums,target);
        int right = rightBound(nums,target);
        return left == -1 ? 0 : right - left + 1;
    }
    int leftBound(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 if(nums[mid] == target){
                right = mid - 1;
            }
        }
        if(left == nums.length){
            return -1;
        }
        return nums[left] == target ? left : -1; 
    }
    int rightBound(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 if(nums[mid] == target){
                left = mid + 1;
            }
        }
        if(right < 0){
            return -1;
        }
        return nums[right] == target ? right : -1;
    }
}

0 赞同 0 条回复

just 普通 2022年11月9日上午10:59

//查找右边界
class Solution {
public:
int helper(vector& nums,int tar){
int l=0,r=nums.size()-1;
while(l<=r){
int mid=l+(r-l)/2;
if(nums[mid]<=tar) l=mid+1;
else r=mid-1;
}
return l;
}
int search(vector& nums, int target) {
int l=helper(nums,target-1);
int r=helper(nums,target);
return r-l;

};

0 赞同 0 条回复

天然普通 2022年11月8日下午11:02

先找到出现第一次的下标，再找最后一次出现的下标，然后做差

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums: return 0
        left1,right1,left2,right2= 0,len(nums)-1,0,len(nums)-1
        while(left1<right1):
            mid = left1+(right1-left1)//2
            if nums[mid] >= target:
                right1 = mid
            else:
                left1 = mid+1

        while(left2 < right2):
            mid = left2+(right2-left2+1)//2
            if nums[mid] > target:
                right2 = mid-1
            else:
                left2 = mid

        if nums[left1]!=target and nums[left2]!=target:return 0
        return left2-left1+1

0 赞同 0 条回复

y 普通 2022年11月8日下午9:43

var search = function(nums, target) {
//   寻找左边界
  let left = 0;
  let right = nums.length - 1;
  while(left <= right) {
      let mid = Math.floor((right + left) / 2);
      if(nums[mid] >= target) {
          right = mid - 1;
      } else {
          left = mid + 1;
      }
  }
  let low = right;

//   寻找右边界
  left = 0;
  right = nums.length - 1;
  while(left <= right) {
      let mid = Math.floor((right + left) / 2);
      if(nums[mid] <= target) {
          left = mid + 1;
      } else {
          right = mid - 1;
      }
  }
  let high = right;
  return high - low;
};

0 赞同 0 条回复

易水寒永久会员 2022年11月8日下午12:14

先寻找左边界

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

0 赞同 0 条回复

庄重普通 2022年11月7日下午7:39

// 思路：
//     1.对于有序数组，优先使用二分查找
//     2.此题中找到找到left = 第一次出现的target 和 right = 最后一次的target
//     3.返回 right -left +1
class Solution {
public:
    int search(vector<int>& nums, int target) {
        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(const vector<int>& nums, int target){
        if(nums.empty() || nums.size() <= 0){
            return -1;
        }
        int left = 0, right = nums.size() - 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(const vector<int>& nums, int target){
        if(nums.empty() || nums.size() <= 0){
            return -1;
        }
        int left = 0, right = nums.size() - 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;
    }
};
//时间复杂度O(logn)
//空间复杂度O(n)

0 赞同 0 条回复

mpweixin用户永久会员 2022年11月7日下午6:58

class Solution {

    public int search(int[] nums, int target) {
        return Find(nums, target) - Find(nums, target - 1);
    }

    int Find(int[] nums, int tar) {
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] <= tar) i = m + 1;
            else j = m - 1;
        }
        return i;
    }
}

我写的要比这个麻烦许多,leetcode给出的最优题解
时间复杂度O(logn)
空间复杂度O（1）

0 赞同 0 条回复

你有点可爱喔普通 2022年11月7日下午4:47

很垃圾

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

0 赞同 0 条回复

T 普通 2022年11月7日下午4:33

class Solution {
    public int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        //寻找右边界
        while(low <= high) {
            int mid = low + ((high - low) >> 1);
            if(nums[mid] <= target)
                low = mid + 1;
            else
                high = mid - 1;
        }
        int right = low;

        if(high >= 0 && nums[high] != target)
            return 0;

        // 寻找左边界
        low = 0;
        high = nums.length - 1;
        while(low <= high) {
            int mid = low + ((high - low) >> 1);
            if(nums[mid] >= target)
                high = mid - 1;
            else
                low = mid + 1;
        }
        int left = high;
        return right - left - 1;
    }
}

0 赞同 0 条回复

优秀市民普通 2022年11月7日下午2:35

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

先找到target-1的右边界，然后找到target的右边界，target-1的右边界就是target的左边界

0 赞同 0 条回复

一只骆驼普通 2022年11月7日上午11:32

先找到最左边的target，再往后找相同的

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

0 赞同 0 条回复

青木普通 2022年11月7日上午11:07

/**
    用二分查找第一个相同的，然后遍历

    时间复杂度O(logn)
    空间复杂度O(1)
 */
class Solution {
    public int search(int[] nums, int target) {
        int ans = 0;
        if(nums == null || nums.length == 0) return ans;

        int start = binarySearch(nums, 0, nums.length - 1, nums.length - 1, target);
        if(start < 0) return ans;
        while(start < nums.length && nums[start] == target){
             start++;
             ans++;
        }

        return ans;
    }

    public int binarySearch(int[] nums, int l, int r, int n, int target){
        while(l <= r){
            int mid = l + ((r - l) >> 1);
            if(nums[mid] >= target){
                r = mid - 1;
            }
            else{
                l = mid + 1;
            }
        }
        if(l > n) return -1;
        return nums[l] == target ? l : -1;
    }
}


/**
    用二分查找第一个相同的，然后再找第二个相同的
    时间复杂度O(logn)
    空间复杂度O(1)
 */
class Solution {
    public int search(int[] nums, int target) {
        int left = binarySearch(nums, target, true);
        int right = binarySearch(nums, target, false) - 1;
        if(left <= right && right < nums.length && nums[left] == target && nums[right] == target){
            return right - left + 1;
        }
        return 0;
    }

    public int binarySearch(int[] nums, int target, boolean lower){
        int l = 0, r = nums.length - 1, ans = nums.length; 
        while(l <= r){
            int mid = l + ((r - l) >> 1);
            if(nums[mid] > target || (lower && nums[mid] >= target)){
                r = mid - 1;
                ans = mid;
            }
            else{
                l = mid + 1;
            }
        }
        return ans;
    }
}

0 赞同 0 条回复

追普通 2022年11月7日上午10:52

class Solution {
public:
    int biarySearch(vector<int> &nums, int target, bool lower){
        int left = 0, right = nums.size() - 1, ans = 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 left = biarySearch(nums, target, true);
        int right = biarySearch(nums, target, false);
        return right - left;
    }
};

使用二分查找法寻找数组中target值的重复情况

0 赞同 0 条回复

是梦终空永久会员 2022年11月7日上午8:39

前天的模板直接用了
时间O(log(n))
空间O(1)

class Solution {
    public int search(int[] nums, int target) {
        int res1 = floor_lower(nums,target);
        int res2 = floor_upper(nums,target);
        if(res1 != -1){
            return res2-res1+1;
        }
        return 0;
    }
    int floor_upper(int[] arr, int target) {
        int len = arr.length;
        int r = len - 1;
        int l = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (arr[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        if(l>0){
            if(arr[l-1] == target){
                return l-1;
            }
        }
        return -1;
    }
    int floor_lower(int[] arr, int target) {
        int len = arr.length;
        int r = len - 1;
        int l = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (arr[mid] >= target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        if(r<len-1){
            if(arr[r + 1] == target){
                return r + 1;
            }
        }
        return  -1;
    }
}

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月7日上午12:48

时间复杂度O（lgn），空间复杂度O（1）

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

0 赞同 0 条回复

So 普通 2022年11月6日下午11:39

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

    public int floor_upper(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (left > 0) {
            if (arr[left - 1] == target) {
                return left - 1;
            }
        }
        return (left < arr.length && arr[left] == target) ? left : -1;
    }

    public int floor_lower(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (arr[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (right < arr.length - 1) {
            if (arr[right + 1] == target) {
                return right + 1;
            }
        }
        return (right >= 0 && arr[right] == target) ? right : -1;
    }
}

时间：O(log(n))，空间：O(1)

0 赞同 0 条回复

cxc 普通 2022年11月6日下午10:40

class Solution {
    public int[] searchRange(int[] nums, int target) {
//拿左区间减去右区间
        return new int[]{upper(nums, target - 1), upper(nums, target) - 1};
    }

    public int upper(int[] arr, int target){//如果都不存在，则返回-1
        int length = arr.length;
        if(arr==null || length < 1) return -1;

        int left = 0;
        int right = length - 1;

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


         return  left <= arr.length-1 ? left : -1;
    }

}

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月6日下午9:10

先查出左区间，再从左往右找
时间复杂度O(logn)

class Solution {
    public int search(int[] nums, int target) {
        int left = Binary_Search(nums,target);
        if(left == -1) return 0;
        int right;
        for(right = left + 1;right < nums.length && nums[right] == nums[left];right++);
        return right - left;
    }
    //搜索当前数组的左边界
    public int Binary_Search(int[] nums,int target){
        int left = 0;
        int right = nums.length;
        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 == nums.length) return -1;
        return nums[left] == target ? left : -1;
    }
}

0 赞同 0 条回复

派大星普通 2022年11月6日下午7:59

class Solution {
   public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0 || nums[0] > target)return 0;
        if(nums.length == 1){
            if(nums[0] == target)return 1;
            else return 0;
        }
        int sum = 0;
        int begin = 0;
        int end = nums.length - 1;
        int middle = 0;
        while(begin != end && middle <= end && middle >= begin){
            middle = (end+begin) / 2;
            if(nums[middle] < target){
                begin = middle + 1;
                middle = (end+begin) / 2;
            } else if (nums[middle] == target) {
                for (int i = begin; i <= middle; i++) {
                    if(nums[i] < target)begin++;
                    else if(nums[i] == target){
                        sum++;
                        begin++;
                    }
                }
                middle = (end+begin) / 2;
            } else if(nums[middle] > target) {
                end = middle-1;
                middle = (end+begin) / 2;
            }
        }
        if(nums[begin] == target)sum++;
        return sum ;
    }
}

0 赞同 0 条回复

Error 普通 2022年11月6日下午6:36

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def helper(tar):
            i, j = 0, len(nums) - 1
            while i <= j:
                m = (i + j) // 2
                if nums[m] > tar:
                    j = m -1
                else:
                    i = m + 1
            return i
        return helper(target) - helper(target - 1)

找出左右边界
时间复杂度 O(logn)

0 赞同 0 条回复

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

共以下 36 个回答

# 回答此问题取消回复

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

共以下 36 个回答

# 回答此问题 取消回复

# 回答此问题取消回复