在排序数组中查找元素的第一个和最后一个位置(leetcode)_数组找到某个元素第一个

给定一个按照升序排列的整数数组nums,和一个目标值target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值target,返回[-1,-1]

示例1：

nums = [5,7,7,8,8,10], target = 8

- 解法一

思路 : 记录目标值第一次出现的下标值,和目标值出现的次数。

- 代码如下

class Solution:
    def searchRange(self, nums, target):
        first = 0
        count = 0
        flag = True
        for i in range(len(nums)):
            if nums[i] == target:
                if first == 0 and flag:
                    first = i
                    flag = False
                count += 1
        if count == 1:
            return [first, first]
        elif count > 1:
            return [first, first + count - 1]
        else:
            return [-1, -1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 解法二
• 思路

利用二分查找法，找到最该目标值最左出现的下标和目标值+1 的下标

代码如下

class Solution02:
    def searchRange(self, nums, target):
        def search_target(target):
            start,end = 0,len(nums) -1
            while start <= end:
                mid = (start + end)//2
                if target < nums[mid]:
                    end = mid - 1
                elif target > nums[mid]:
                    start = mid + 1
                else:
                    end = mid -1 # 往左移，找到第一次出现的下标
            return start
        start = search_target(target)
        end = search_target(target+1) - 1

        if target in nums:
            return [start,end]
        return [-1,-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

很python 的写法

class Solution01:

    def searchRange(self, nums, target):
        if target in nums:
            first = nums.index(target)
            return [first, first + nums.count(target) - 1]
        return [-1, -1]
     

1
2
3
4
5
6
7
8
9