leetcode34---在排序数组中查找元素的第一个和最后一个位置

leetcode34—在排序数组中查找元素的第一个和最后一个位置

---

题意简述

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

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

示例 1:

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

示例 2:

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

---

解题分析

• 二分查找

分析: 有序,而且从时间复杂度要求上都能想到二分法求解.
	这里的关键是如何写好这样的二分.通过本文也算自己
	总结以下这两种二分我更容易理解的版本.

• 参考代码

java

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int f_low = 0;
        int e_low = -1;
        int f_top = nums.length; //确定区间时很多喜欢表达这样的概念,即[)(前开后闭)
        int e_top = nums.length - 1;
        int[] ans = {-1, -1};
        //f_low 落到查找元素的第一个
        while(f_low < f_top) {
            int mid = (f_low + f_top) >> 1;
            if(nums[mid] < target) {
                f_low = mid + 1;
            } else {
                f_top = mid;
            }
        }
        if(f_low != nums.length && nums[f_low] == target) ans[0] = f_low;
        //e_top 落到查找元素的最后一个
        while(e_low < e_top) {
            int mid = (e_low + e_top + 2) >> 1;
            if(nums[mid] > target) {
                e_top = mid - 1;
            } else {
                e_low = mid;
            }
        }
        if(e_top != -1 && nums[e_top] == target) ans[1] = e_top;
        return ans;
    }
}

go

func searchRange(nums []int, target int) []int {
    ans := [2]int{-1,-1}
    length := len(nums)
    front_low, end_low := 0, -1
    front_top, end_top := length, length - 1
    for front_low < front_top {
        mid := (front_low + front_top) >> 1
        if nums[mid] < target {
            front_low = mid + 1
        } else {
            front_top = mid
        }
    }
    if front_low != length && nums[front_low] == target {
        ans[0] = front_low
    }
    for end_low < end_top {
        mid := (end_low + end_top + 2) >> 1
        if nums[mid] > target {
            end_top = mid - 1
        } else {
            end_low = mid
        }
    }
    if end_top != -1 && nums[end_top] == target {
        ans[1] = end_top
    }
    return ans[:]
}