C/C++教程

力扣-34题 在排序数组中查找元素的第一个和最后一个位置(C++)- 二分法

本文主要是介绍力扣-34题 在排序数组中查找元素的第一个和最后一个位置(C++)- 二分法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
题目如下:
在这里插入图片描述

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> result={-1,-1};

        int low=0,high=nums.size()-1,mid;
        bool flag=false;

        while(low<=high){
            mid=(low+high)/2;

            if(nums[mid]>target) high=mid-1;
            else if(nums[mid]<target) low=mid+1;
            else if(nums[mid]==target) {flag=true;break;}
        }


        if(flag){
            result[0]=result[1]=mid;//确定当前元素的区间,进而双指针法向两边外扩

            for(int i=mid-1;i>=0;i--){
                if(nums[i]==target) result[0]=i;
                else break;
            }
            
            for(int i=mid+1;i<nums.size();i++){
                if(nums[i]==target) result[1]=i;
                else break;
            }

        }

        return result;
    }
};
这篇关于力扣-34题 在排序数组中查找元素的第一个和最后一个位置(C++)- 二分法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!