LeeCode 34. 在排序数组中查找元素的第一个和最后一个位置 剑指Offer 53 在排序的数组中查找数字

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

https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

剑指Offer 053 在排序的数组中查找数字

首先要说明一下啊，这两题看起来是不一样的，但是其实你自己的理解题目，就会发现，这两题不过是换汤不换药的题目，完全就是换了一个马甲而已。
这题的主要解决的是先找到左边的目标数的位置，然后再找右边的目标数的位置，因为LeetCode题目中有中有明确的说，需要在对数的时间复杂度来完成这道题，所以肯定走的是二分思想了。
那么问题就是变成了，你要用二分思想找到目标值的最左边的那个数字；然后再用二分思想来找出目标数的最左边的数。
以下代码，我用来两个二分思想的函数来分别查找那个目标数，不过这里的跳出条件变了，如果在原来的和目标值相等的基础上，变成了还要分别是最左和最右的数才可以退出

	/*** 寻找左右边的第一个K的位置* @param data* @param start* @param end* @param len* @param target* @return*/private int getFirstKIndex(int[] data, int start, int end, int len, int target) {
    if (start < end) {
    return -1;}int mid = start +((end - start) >> 1);if (data[mid] == target) {
    // 确定这个mid的值是最左边的值了if ((mid > 0 && data[mid - 1] != target) || mid == 0) {
    return mid;} else {
    end = mid - 1;}} else if (data[mid] > target) {
    end = mid - 1;} else {
    start = mid + 1;}return getFirstKIndex(data, start, end, len, target);}/*** 寻找左边的第一个K的位置* @param data* @param start* @param end* @param len* @param target* @return*/private int getLastKIndex(int[] data, int start, int end, int len, int target) {
    if (start > end) {
    return - 1;}int mid = start + ((end - start) >> 1);if (data[mid] == target) {
    // 确定这个mid的值是最右边的值了if ((mid < len - 1 && data[mid + 1] != target) || mid == len - 1) {
    return mid;} else {
    start = mid + 1;}} else if (data[mid] > target) {
    end = mid - 1;} else {
    start = mid + 1;}return getLastKIndex(data, start, end, len, target);}public int[] searchRange(int[] nums, int target) {
    int[] ans = {
    -1, -1};if (nums == null || nums.length == 0) {
    return ans;}int firstKIndex = getFirstKIndex(nums, 0, nums.length - 1, nums.length , target);int lastKIndex = getLastKIndex(nums, 0, nums.length - 1, nums.length , target);if (firstKIndex != -1 && lastKIndex != -1) {
    ans[0] = firstKIndex;ans[1] = lastKIndex;}return ans;}

以上两个时间复杂都是$O(logN)$