【LeetCode每日一题】——34.在排序数组中查找元素的第一个和最后一个位置

• 一【题目类别】
• 二【题目难度】
• 三【题目编号】
• 四【题目描述】
• 五【题目示例】
• 六【题目提示】
• 七【解题思路】
• 八【时间频度】
• 九【代码实现】
• 十【提交结果】

• 二分查找

• 中等

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

• 给你一个按照非递减顺序排列的整数数组 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 < = n u m s . l e n g t h < = 1 0 5 0 <= nums.length <= 10^5 0<=nums.length<=105
• − 1 0 9 < = n u m s [ i ] < = 1 0 9 -10^9 <= nums[i] <= 10^9 −109<=nums[i]<=109
• nums 是一个非递减数组
• − 1 0 9 < = t a r g e t < = 1 0 9 -10^9 <= target <= 10^9 −109<=target<=109

• 主要还是二分查找的思路
• 如果数组长度为0说明空数组，直接返回题目要求的结果即可
• 先找左边界，所以要向下取整（mid = (left + right) / 2），向左收缩
• 再找右边界，所以要向上取整（mid = (left + right + 1) / 2），向右收缩
• 主要找完左边界要判断是否找到了，如果没找到返回题目要求的结果即可
• 最后返回左边界和右边界构成的数组

• 时间复杂度： O ( l o g 2 N ) O(log_{2}N) O(log2​N)，其中 N N N为数组元素个数
• 空间复杂度： O ( 1 ) O(1) O(1)

1. Java语言版

package BinarySearch;

import java.util.Arrays;

public class p34_FindTheFirstAndLastPositionOfAnElementInASortedArray {

    public static void main(String[] args) {
        int[] nums = {5, 7, 7, 8, 8, 10};
        int[] res = searchRange(nums, 8);
        System.out.println("res " + Arrays.toString(res));
    }

    public static int[] searchRange(int[] nums, int target) {
        int[] res = new int[2];
        if (nums.length == 0) {
            res[0] = -1;
            res[1] = -1;
            return res;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (left >= nums.length || nums[left] != target) {
            res[0] = -1;
            res[1] = -1;
            return res;
        }
        res[0] = left;
        left = 0;
        right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right + 1) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        res[1] = right;
        return res;
    }

}

2. C语言版

#include

int* searchRange(int* nums, int numsSize, int target, int* returnSize)
{
	int* res = (int*)malloc(sizeof(int) * 2);
	*returnSize = 2;
	if (numsSize == 0)
	{
		res[0] = -1;
		res[1] = -1;
		return res;
	}
	int left = 0;
	int right = numsSize - 1;
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (nums[mid] >= target)
		{
			right = mid - 1;
		}
		else
		{
			left = mid + 1;
		}
	}
	if (left >= numsSize || nums[left] != target)
	{
		res[0] = -1;
		res[1] = -1;
		return res;
	}
	res[0] = left;
	left = 0;
	right = numsSize - 1;
	while (left <= right)
	{
		int mid = (left + right + 1) / 2;
		if (nums[mid] <= target)
		{
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}
	}
	res[1] = right;
	return res;
}

1. Java语言版
   

2. C语言版