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

题目描述

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

image-20230305132114938

思路分析

等于给定值的第一个元素和最后一个元素

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

func searchRange(nums []int, target int) []int {
	left, right := searchLeft(nums, target), searchRight(nums, target)
	return []int{left, right}
}

func searchLeft(nums []int, target int) int {
	left, right := 0, len(nums)-1
	first := -1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] > target {
			right = mid - 1
		} else if nums[mid] < target {
			left = mid + 1
		} else {
			first = mid
			right = mid - 1
		}
	}
	return first
}

func searchRight(nums []int, target int) int {
	left, right := 0, len(nums)-1
	last := -1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] > target {
			right = mid - 1
		} else if nums[mid] < target {
			left = mid + 1
		} else {
			last = mid
			left = mid + 1
		}
	}
	return last
}

🍏 点击查看 Java 题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = searchLeft(nums, target);
        int right = searchRight(nums, target);
        return new int[]{left, right};
    }

    public int searchLeft(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int first = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                first = mid;
                right = mid - 1;
            }
        }
        return first;
    }

    public int searchRight(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int last = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                last = mid;
                left = mid + 1;
            }
        }
        return last;
    }
}

相似题目

题目 难度 题解
第一个错误的版本 Easy  
本文作者:
本文链接: https://hgnulb.github.io/blog/81925119
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！