labuladong commented 1 year ago

本期打卡已结算完成。报名最新一期的打卡活动点这里

Susan19996 commented 1 year ago

34 https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/ 704 https://leetcode.com/problems/binary-search/

KenanHuang commented 1 year ago

https://leetcode.cn/problems/binary-search/solutions/2374783/ji-chu-er-fen-cha-zhao-by-kenanhuang99-y5o8/ https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/2378210/dui-zhang-gong-zheng-de-zuo-you-jie-sou-v5ff7/

dh0072 commented 1 year ago

Q704. Binary Search https://leetcode.com/problems/binary-search/discuss/3869008/Java-Solution-binary-search-left-right

Q34. Find First and Last Position of Element in Sorted Array https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/discuss/3869244/Java-Solution-Binary-Search-with-left-right-condition

macksonyli21826 commented 1 year ago

https://leetcode.cn/problems/binary-search/solutions/2374845/problem-704-er-fen-cha-zhao-by-hachi-lok-uhgw/

ShaodongGu commented 1 year ago

Q34 https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/3869423/binary-search-w-boundary/

jojoss commented 1 year ago

[704. Binary Search] https://leetcode.com/problems/binary-search/solutions/3869578/java-solution/

Reset0808 commented 1 year ago

https://leetcode.cn/problems/binary-search/solutions/2374905/er-fen-cha-zhao-by-2ba4zmutle-164l/

wangyin717 commented 1 year ago

[704] 二分查找 https://leetcode.cn/problems/binary-search/solutions/2374891/704-er-fen-cha-zhao-by-wangyin717-21ie/ [34] 在排序数组中查找元素的第一个和最后一个位置 https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/2374943/34-zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-ayks/

GodisinHisHeaven commented 1 year ago

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/3869746/python-solution/

zexianw12 commented 1 year ago

Q704： https://leetcode.cn/problems/binary-search/solutions/2375021/er-fen-cha-zhao-by-vvenan-aylm/

Rayden-Xu commented 1 year ago

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/2375073/zui-rong-yi-li-jie-de-zhi-zhen-zuo-you-k-w284/

最容易理解的思路，此题难点在于怎么找到和target相同的值 ties情况，因为是非递减数组，那么我们找到了一个值，其ties一定就在此值的左右附近，所以左右扩散指针 i=j=mid就非常有用来处理找到值之后ties的情况。如果第一次没找到，就进行传统二分的边界收缩，最后没找到返回 [-1,-1] ，最坏情况下可能会到O(N)

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        #二分查找+左右扩散
        left = 0
        right = len(nums)-1
        while left<=right :
            mid = left + (right -left)//2
            if nums[mid]==target:
                i = j = mid # mid处定两个指针左右扩散
                while j<=len(nums)-1 and nums[j]==target: #检查和target一样的值
                    j+=1
                while i>=0 and nums[i]==target:
                    i-=1
                return [i+1,j-1]
            elif nums[mid]>target: #没一下找到的情况下进行传统二分收缩边界
                right = mid-1
            else:
                left = mid+1
        return [-1,-1] #如果都没有找到直接返回 [-1，-1]

两次二分左右边界，分别check边界，时间复杂度 O(nlogn)

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        return [self.left_bound(nums, target), self.right_bound(nums, target)]

    def left_bound(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        # 搜索区间为 [left, right]
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                # 搜索区间变为 [mid+1, right]
                left = mid + 1
            elif nums[mid] > target:
                # 搜索区间变为 [left, mid-1]
                right = mid - 1
            elif nums[mid] == target:
                # 收缩右侧边界
                right = mid - 1
        # 检查出界情况
        if left >= len(nums) or nums[left] != target: 

            return -1
        return left

    def right_bound(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            elif nums[mid] == target:
                # 这里改成收缩左侧边界即可
                left = mid + 1
        # 这里改为检查 right 越界的情况，见下图
        if right < 0 or nums[right] != target: 

            return -1
        return right

wangbingran163 commented 1 year ago

https://leetcode.cn/problems/binary-search/solutions/2375187/er-fen-cha-zhao-by-dao-yan-jian-yan-yuan-qn70/

ConnieLuksc commented 1 year ago

https://leetcode.com/problems/binary-search/solutions/3870428/binary-search-in-python/

Catboss1999 commented 1 year ago

左闭右闭/左闭右开两种二分： https://leetcode.cn/problems/binary-search/solutions/2375247/zuo-bi-you-kai-zuo-bi-you-bi-liang-chong-5gik/ 二分+左右指针： https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/2375381/er-fen-cha-zhao-zuo-you-zhi-zhen-by-cat-44mj4/

vanessacz commented 1 year ago

Binary Search https://leetcode.com/problems/binary-search/solutions/3870827/java-binary-search-solution/

AlanKang98 commented 1 year ago

https://leetcode.cn/problems/binary-search/solutions/2375520/zhu-yi-bian-jie-kong-zhi-by-alank-usyd-2cq0/

txhj1996 commented 1 year ago

https://leetcode.cn/problems/binary-search/solution/er-fen-cha-zhao-by-6ifted-vvrightj26-w9h5/

sdyin commented 1 year ago

34.排序数组中查找元素的第一个和最后一个位置 https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/2375569/34pai-xu-shu-zu-zhong-cha-zhao-yuan-su-d-jmvz/

Xiaolin8991 commented 1 year ago

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/2375612/er-fen-cha-zhao-by-xiao-lin-mz-vxdw/

chen-huanxin commented 1 year ago

34： https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/2375669/cpper-fen-cha-zhao-0806-34-zai-pai-xu-sh-g6eh/

hxingjie commented 1 year ago

704.https://leetcode.cn/problems/binary-search/solutions/2375609/er-fen-cha-zhao-by-betodea-epqe/ 34.https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/2375690/zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-su-zu0v/

jiuxi521 commented 1 year ago

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/2375833/er-fen-cha-zhao-zuo-you-du-bi-by-lean-in-ehap/

Jingzhenzxz commented 1 year ago

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/2375837/er-fen-sou-suo-bian-jie-wen-ti-by-distra-gh9x/

Problem: 34. 在排序数组中查找元素的第一个和最后一个位置

[TOC]

思路

在二分搜索边界问题中，while 循环里不能 return，所以我们必须在while循环后return，这时候return又分为两种情况，一种是在while循环中找到了目标边界，那么就返回这个索引，另一种就是没找到，那就返回-1。

复杂度

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

Code


class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{left_bound(nums, target), right_bound(nums, target)};
    }

    int left_bound(int[] nums, int target) {
        int left = 0;
        int 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;
            }
        }
        // while 循环前，left 是整个数组的左边界，while 循环后，left 是目标值的左边界。
        // 检查出界情况，因为 left 是一直增加的，所以它一定大于 0，且只有两种情况，要么越过右边界，要么没越过，没越过的话就看它对应的值是否等于 target。由于结束条件是 left = right + 1，所以这里也可以换成 right，但要注意，我们本质上用的还是 left 满足的关系，因为 right 指的是右边界
        // if (right >= nums.length - 1 || nums[right + 1] != target)
        if (left >= nums.length || nums[left] != target) {
            return -1;
        }
        return left;
    }

    int right_bound(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) {
                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;
    }
}