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

系统管理员 2022-12-25 08:57 157阅读 0赞

> leetcode 34题 \[medium\]  
> 中：[在排序数组中查找元素的第一个和最后一个位置][Link 1]  
> 英：[Find First And Last Position Of Element In Sorted Array][]  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]

### 题解 ###

1.  两次(边界)二分查找（[二分查找详解可以看看这篇博客][Link 2]）
2.  时间复杂度：O(logn)
3.  空间复杂度：O(1)
4.  实现
    
        /** * @param {number[]} nums * @param {number} target * @return {number[]} */
        var searchRange = function(nums, target) { 
            /** * 两次二分查找（左、右边界二分查找） * 时间复杂度：O(logn) * 空间复杂度：O(1) */
            // 预处理（无）
        
            // 左边界
            let l = 0, r = nums.length - 1;
            while(l <= r){ 
                let mid = l + Math.floor((r - l) / 2);
                if(target < nums[mid]){ 
                    r = mid - 1;
                }
                else if (target > nums[mid]){ 
                    l = mid + 1;
                }
                else{ 
                    r = mid - 1;
                }
            }
            // 循环退出条件 l = r + 1; l: 左边界
            if(l >= nums.length || nums[l] !== target) return [-1, -1];
            let leftBorder = l;
        
            // 右边界（l 复用 leftBorder）
            r = nums.length - 1;
            while(l <= r){ 
                let mid = l + Math.floor((r - l) / 2);
                if(target < nums[mid]){ 
                    r = mid - 1;
                }
                else if (target > nums[mid]){ 
                    l = mid + 1;
                }
                else { 
                    l = mid + 1;
                }
            }
            // 循环退出条件 l = r + 1, r = l - 1; r: 右边界
            return [leftBorder, r];
        };

[Link 1]: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
[Find First And Last Position Of Element In Sorted Array]: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]: /images/20221120/8dcdda21414a484ca6382563389bb390.png
[Link 2]: https://blog.csdn.net/SJ1551/article/details/109451466