python查找列表元素个数,python list查找元素位置

1. 题目链接34. 在排序数组中查找元素的第一个和最后一个位置 2. 题目描述

给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1

输入nums  [5,7,7,8,8,10], target  8输出[3,4]

示例 2

输入nums  [5,7,7,8,8,10], target  6输出[-1,-1]

示例 3

输入nums  [], target  0输出[-1,-1]

提示

0 < nums.length < 105-109 < nums[i] < 109nums 是一个非递减数组-109 < target < 109 3. 寻找左边界的思路 用x表示该元素resLest表示左边界resRight表示右边界左边区间都是小于x的右边区间包括左边界都是大于等于x的mid的落点情况如下 当mid落在[left,resLeft-1]区间的时候也就是arr[mid]<target说明[leftmid]都是可以舍去的此时更新left到mid1的位置继续在[mid1,right]上寻找左边界当mid落在[resLeft,right]的区间的时候也就是arr[mid]>target说明[mid1right]因为mid可能是最终结果不能舍去是可以舍去的此时更新right到mid的位置继续[left,mid]上寻找左边界 由此就可以通过二分来快速寻找左边界

注意事项找中间元素需要向下取整

因为后续继续移动指针的时候

左指针leftmid1是会向后移动的因此区间是会缩小的

右指针rightmid可能会原地踏步比如如果向上取整的话如果剩下12两个元素的left1right2mid2。更新区间之后leftright,mid的值没有改变就会陷入死循环

4. 寻找有右边界的思路 用x表示该元素resLest表示左边界resRight表示右边界左边区间包括右边界[left,resRight]都是小于等于x的右边区间[resRight1,right]都是大于x是的mid的落点情况如下 当我们的mid落在[leftresRight]区间的时候也就是arr[mid]<target说明[left,mid-1]mid不可以舍去因为有可能是最终结果都是可以舍去的此时更新left到mid的位置当mid落在[resRight1,right]的区间的时候也就是arr[mid]>target说明[mid,right]内的元素是可以舍去的此时更新right到mid-1的位置 由此就可以通过二分来快速寻找右边界

注意事项找中间元素需要向上取整

因为后续继续移动指针的时候

左指针 left mid 可能会原地踏步⽐如如果向下取整的话如果剩下 1,2 两个元
素 left 1 right 2mid 1 。更新区间之后 leftrightmid 的值
没有改变就会陷⼊死循环。
右指针 right mid - 1 是会向前移动的因此区间是会缩⼩的
因此⼀定要注意当right mid 的时候要向下取整。

5. 算法流程 首先判断数组是否为空如果为空则返回{-1, -1}表示无解。初始化左指针left为0右指针right为数组长度减1。通过二分查找找到目标元素的起始位置。循环条件是左指针left小于右指针right计算中间位置mid如果中间位置的元素小于目标元素则目标元素可能在右半部分更新左指针left为mid 1。如果中间位置的元素大于等于目标元素则目标元素可能在左半部分更新右指针right为mid。循环结束后左指针left指向的位置就是目标元素的起始位置。判断数组中是否存在目标元素如果左指针left指向的元素不等于目标元素则不存在目标元素返回{-1, -1}表示无解。将目标元素的起始位置保存在变量begin中。通过二分查找找到目标元素的结束位置。重新初始化左指针left为0右指针right为数组长度减1。循环条件是左指针left小于右指针right计算中间位置mid如果中间位置的元素大于目标元素则目标元素可能在左半部分更新右指针right为mid - 1。如果中间位置的元素小于等于目标元素则目标元素可能在右半部分更新左指针left为mid。循环结束后右指针right指向的位置就是目标元素的结束位置。返回包含起始位置和结束位置的结果数组{begin, right}作为最终答案。 6. C算法代码

class Solution {public:    vector<int> searchRange(vector<int>& nums, int target) {        //处理边界情况        if(nums.size()0) return {-1,-1};        int begin0;        //二分左端点        int left0,rightnums.size()-1;        while(left<right)        {            int midleft(right-left)/2;            if(nums[mid]<target) leftmid1;            else rightmid;        }        //判断的是否有结果        if(nums[left]!target)        return {-1,-1};        else beginleft;        //二分右端点        left0,rightnums.size()-1;        while(left<right)        {            int midleft(right-left1)/2;            if(nums[mid]>target)  rightmid-1;            else leftmid;        }        return {begin,right};    }};