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

以你之姓@ 2022-02-27 05:52 133阅读 0赞

*  题目描述：
    
        给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
        
        你的算法时间复杂度必须是 O(log n) 级别。
        
        如果数组中不存在目标值，返回 [-1, -1]。
        
        示例 1:
        
        输入: nums = [5,7,7,8,8,10], target = 8
        输出: [3,4]
        示例 2:
        
        输入: nums = [5,7,7,8,8,10], target = 6
        输出: [-1,-1]
 *  分析：由于是在有序数组中查找某个数，故很容易想到首先使用二分查找到该数，因为是有序的，如果这个数存在多个，则肯定是在左边或右边，然后从该位置往左往右遍历，这步操作相当于常数时间复杂度，即整体时间复杂度为O(logN) + O(1)，即符合O(logN)的时间复杂度要求。
    
        class Solution { 
            public int[] searchRange(int[] nums, int target) { 
                int first = -1;
                int last = -1;
                
                int begin = 0;
                int end = nums.length-1;
                while (begin <= end) { 
                    int mid = begin + (end-begin)/2;
                    if (nums[mid]==target) { 
                        first = last = mid;
                        int left = mid-1;
                        int right = mid+1;
                        while(left >= 0 && nums[left]==target) { 
                            first = left--;
                        }
                        while(right <= nums.length-1 && nums[right]==target) { 
                            last = right++;
                        }
                        break;
                    } else { 
                        if (nums[mid] > target) { 
                            end = mid-1;
                        } else { 
                            begin = mid+1;
                        }
                    }
                }
                
                return new int[]{ first, last};
            }
        }