C语言力扣第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 <= nums.length <= 105
- 109 <= nums[i] <= 109
nums 是一个非递减数组
- 109 <= target <= 109
要求时间复杂度O（logn)

来源：力扣（LeetCode）
链接：https ://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

方法一：

先用二分查找找到对应位置，之后再定义两个变量i、j往前后两个方向查找，若相同则更新、不相同直接返回ans

方法二：

1.特殊情况的处理
(1) 当数组为空时的处理,数组为空，numsSize=0，所以对numsSize==0返回-1,-1
(2) 当目标值不在数组范围内时，返回-1,-1
(3) 当数组第一个与最后一个元素都等于目标值target时，直接返回0,numsSize-1
2.了解二分查找完成后left和right的位置，当while条件为left<=right时，
循环结束后，left的位置是目标值的右侧，right是目标值的位置(目标不存在就是目标值的左侧)
所以我们查找目标值的区间，就是查找目标值-1和目标值的left的位置
示例:nums[]={1,2,3,5,5,6,7,9,10}
目标值是5，我们查找4和5的left的值就是3和5（这是下标）
此时3就是左边界，右边界就是目标值5的left-1，及4
3.当数组中没有目标值，经过第二步的查找，当存在时，左边界<=右边界,
反之则数组中不存在目标，返回-1,-1

 #define _CRT_SECURE_NO_WARNINGS
 #include <stdio.h>
 #include <string.h>
#include<stdbool.h>

int* searchRange2(int* nums, int numsSize, int target, int* returnSize) 
{
	int low = 0, high = numsSize - 1, mid = (numsSize-1) / 2;
	int i = 0, j = 0;
	int* ans = (int*)malloc(sizeof(int) * 2);
	*returnSize = 2;
	while (low <= high)//{ 5,7,7,8,8,10 };
	{
		if (target > nums[mid])
		{
			low = mid+1;
			mid = (low + high) / 2;
		}
		if (target < nums[mid])
		{
			high = mid-1;
			mid = (low + high) / 2;
		}
		if (target == nums[mid])
			break;
	}
	if (low > high)
	{
		ans[0] = -1;
		ans[1] = -1;
		return ans;
	}
	while (nums[mid - i] == target || nums[mid + j] == target)
	{
		if (nums[mid - i] == target)
		{
			ans[0] = mid - i;
			i++;
		}
		if (nums[mid + j] == target)
		{
			ans[1] = mid + j;
			j++;
		}
	}

	return ans;
}
int search(int*nums, int numsSize, int target)
{
	int begin = 0;
	int end = numsSize - 1;
	while (begin <= end)
	{
		int step = begin + (end - begin) / 2;
		if (target >= nums[step])
			begin = step + 1;
		else
			end = step - 1;
	}
	return begin;
}
int* searchRange1(int* nums, int numsSize, int target, int* returnSize)
{
	*returnSize = 2;
	int*ans = (int*)malloc(sizeof(int) * 2);
	ans[0] = ans[1] = -1;
	if (numsSize == 0)
		return ans;
	if (target<nums[0] || target>nums[numsSize - 1])
		return ans;
	if (target == nums[0] && target == nums[numsSize - 1])
	{
		ans[0] = 0;
		ans[1] = numsSize - 1;
		return ans;
	}
	ans[0] = search(nums, numsSize, target - 1);
	ans[1] = search(nums, numsSize, target) - 1;
	if (ans[0] > ans[1])
		ans[0] = ans[1] = -1;
	return ans;
}



int main()
{
	int nums[1] = { 1};
	int target = 1;
	int i = 2;
	int j = 0;
	int numsSize = sizeof(nums) / sizeof(int);
	int* returnSize = &i;
	int* result = NULL;
	result = searchRange1(nums, numsSize, target, returnSize);
	for (j = 0; j < 2; j++)
		printf("%d", *(result + j));
}