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

概述

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

分析

• 题目要求时间复杂度$O(logN)$，并且给出的是一个有序数组中插入目标值的问题，容易想到使用二分法

• 但是注意到下的示例中，数组中可以有重复元素的，所以当你每次二分查找到target时，左右两边都有可能还有target，所以对两边应该继续使用二分法

思路

二分思路？

略

如何实现左右两边继续二分？

• 首先，因为不知道要向两边查找多少次，为了避免代码重复，应该考虑将二分的代码提取出来
• 然后，因为每次有二分有方向，所以二分的函数应该需要有一个标志来判断方向

代码

class Solution {
public:
    int min_left = -1, max_right = -1;
    void Binary_Search(int L, int R, vector<int>& nums, int target,bool flag) {		// 二分函数
        while (L <= R ) {
            int mid = (R - L) / 2 + L;
            if (target == nums[mid]) { 
                if (!flag) {		// flag是用来判断二分方向的
                    min_left = mid;
                    Binary_Search(L, mid - 1, nums, target,flag);
                }
                else {
                    max_right = mid;
                    Binary_Search(mid + 1, R, nums, target, flag);
                }
                break;
            } else if (target > nums[mid])  
                L = mid + 1;
            else   
                R = mid - 1;
        }
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        int L = 0, R = nums.size() - 1;
        while (L <= R ) {
            int mid = (R - L) / 2 + L;
            if (target == nums[mid]) {	// 第一次找到target后，需要继续向左边和右边二分
                min_left = max_right = mid;
                Binary_Search(L, mid - 1, nums, target, false);     // 往左二分找最左边的target
                Binary_Search(mid + 1, R, nums, target, true);    	// 往右二分找最右边的target
                break;
            } else if (target > nums[mid])  
                L = mid + 1;
            else   
                R = mid - 1;
        }
        return {min_left, max_right};
    }
};