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

题目要求

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

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

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

样例 #1

输入 #1

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

输出 #1

1
[3,4]

样例 #2

输入 #2

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

输出 #2

1
[-1,-1]

样例 #3

输入 #3

1
nums = [], target = 0

输出 #3

1
[-1,-1]

提示

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

解题思路

看到提示说明，时间复杂度为O(log n)，想到用二分法查找
1.先进行二分法查找，找到目标值的位置
2.在目标值左侧进行二分查找，找到目标值的第一个位置
3.在目标值右侧进行二分查找，找到目标值的最后一个位置

代码展示

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
int* searchRange(int* nums, int numsSize, int target, int* returnSize){
    int left,right,mid;
    int local,local1,local2;
    int *LOCAL;
    LOCAL=(int*)malloc(2*sizeof(int));
    *returnSize=2;
    if(numsSize!=0){
    left=0;
    right=numsSize-1;
    mid=(left+right)/2;
    while(mid>=0&&mid<numsSize&&nums[mid]!=target&&left<right){
        if(nums[mid]<target){
            left=mid+1;
        }
        else{
            right=mid-1;
        }
        mid=(left+right)/2;
    }
    if(left>right||nums[mid]!=target){
        local1=-1;
        local2=-1;
    }
    else{
        local=mid;
        right=mid;
        left=0;
        mid=(left+right)/2;
        while(!((mid==0||(mid!=0&&nums[mid-1]!=target))&&nums[mid]==target)){
            if(nums[mid]==target){
                right=mid-1;
            }
            else{
                left=mid+1;
            }
            mid=(left+right)/2;
        }
        local1=mid;
        left=local;
        right=numsSize-1;
        mid=(left+right)/2;
        while(!((mid==numsSize-1||(mid!=numsSize-1&&nums[mid+1]!=target))&&nums[mid]==target)){
            if(nums[mid]==target){
                left=mid+1;
            }
            else{
                right=mid-1;
            }
            mid=(left+right)/2;
        }
        local2=mid;
    }
    }
    else{
        local1=-1;
        local2=-1;
    }
    LOCAL[0]=local1;
    LOCAL[1]=local2;
    return LOCAL;
}

解法优化

不必进行第一次二分查找找到目标值，直接进行二分查找找第一个位置和最后一个位置

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#if defined(MY_TEST)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

static int* str_to_array(char* str, int* numsSize) {
	int* arr = malloc(4096 * sizeof(int)), n = 0;
	char buf[4096], * p;
	strcpy(buf, str);
	for (p = strtok(buf, ", []"); p != NULL; p = strtok(NULL, ", []"))
		arr[n++] = strtol(p, 0, 0);
	*numsSize = n;
	return arr;
}

int* searchRange(int* nums, int numsSize, int target, int* returnSize);

static void test(char* str, int target) {
	int n, * arr = str_to_array(str, &n);
	int* res = searchRange(arr, n, target, &n);
	printf("[%d,%d]\n", res[0], res[1]);
}

int main(void)
{
	test("[5, 7, 7, 8, 8, 10]", 8);  // �����[3, 4]
	test("[5, 7, 7, 8, 8, 10]", 6);  //	�����[-1, -1]
	test("[]", 0); //		�����[-1, -1]
	return 0;
}

#endif

int* searchRange(int* nums, int numsSize, int target, int* returnSize)
{
    int left = 0, right = numsSize, mid;
    static int ans[2];

    ans[0] = ans[1] = -1;

    while (left < right) {
        mid = (left + right) / 2;
        if (nums[mid] >= target)
            right = mid;
        else
            left = mid + 1;
    }
    if (left == numsSize || nums[left] != target)
        return ans;
    ans[0] = left;

    left = 0;
    right = numsSize;
    while (left < right) {
        mid = (left + right) / 2;
        if (nums[mid] <= target)
            left = mid + 1;
        else
            right = mid;
    }
    ans[1] = left;
    return ans;
}