二分查找 练习记录：

题目描述：

在排序数组中查找元素的第一个和最后一个位置：给定一个增序的整数数组和一个值，查找该值第一次和最后一次出现的位置。

示例如下:

 输入：nums = [1,3,6,,6,8,9], target= 6
输出：[2,3]

输入：nums = [1,3,6,,6,8,9], target= 7
输出：[-1，-1]

输入：nums = [], target= 6
输出：[-1,-1]  

思路：

思路一：双指针的思路，分别从数组左和右开始遍历数组寻找目标值，分别将值存入返回的数组中。该方法的时间复杂度为O(n),因为需要遍历整个数组。

思路二：使用二分法，分别寻找目标值在数组的最左位置和最右的位置，相当于遍历数组两次来寻找第一次出现的位置和最后一次出现的位置。找第一次出现的位置使用二分法找到目标值后继续 向左 二分查找目标值（因为当前找到的目标值不一定是第一次出现），同理找最后一次出现的位置时，当找到目标值后继续向右查找目标值（因为当前找到的目标值不一定是第一次出现）。实际时间复杂度为2log(n)≈log(n)。

代码实现：

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

 # include <stdio.h>
#include<stdlib.h>
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
//思路一：双指针的思路
int* searchRange(int* nums, int numsSize, int target, int* rereturnSize) {
	int* ret = (int*)malloc(2*sizeof(int));
	*rereturnSize = 2;
	if (numsSize == 0 )
	{
		ret[0] = -1; ret[1] = -1;
		return ret;
	}
	int left = 0, right = numsSize - 1;
	ret[0] = -1; ret[1] = -1;
	 bool  left_flag = false, right_flag = false;
	while ((left <numsSize && right >=0))
	{
		if ( (ret[0] == -1) || (ret[1] == -1))
		{
			if (nums[left] == target && left_flag == false)
			{
				ret[0] = left;
				left++;
				left_flag = true;
			}
			else
			{
				left++;
			}
			if (nums[right] == target && right_flag == false)
			{
				ret[1] = right;
				right--;
				right_flag = true;
			}
			else
			{
				right--;
			}
		}
		else
		{
			break;
		}
	}
	if (ret[0]!= -1 &&ret[1] != -1)
	{
		return ret;
	}
	else
	{
		ret[0] = -1; ret[1] = -1;
		return ret;
	}
}
//思路二：使用二分法
int* searchRange(int* nums, int numsSize, int target, int* rereturnSize)
{
	int* ret = (int*)malloc(2 * sizeof(int));
	if (numsSize == 0)
	{
		ret[0] = -1; ret[1] = -1;
		return ret;
	}
	int left = 0, right = numsSize - 1;
		ret[0] = -1; ret[1] = -1;
	while (left<=right)
	{
		int mid = left + (right - left+1) / 2;
		if (nums[mid] == target)
		{
			ret[0] = mid;
			right = mid-1;
		}
		else if ( target > nums[mid])
		{
			left = mid+1;
		}
		else
		{
			right = mid-1;
		}
	}
 left = 0, right = numsSize - 1;
	while (left <= right)
	{
		int mid = left + (right - left+1) / 2;
		if (nums[mid] == target)
		{
			ret[1] = mid;
			left = mid+1;
		}
		else if (target > nums[mid])
		{
			left = mid+1;
		}
		else
		{
			right = mid-1;
		}
	}
	return ret;
}
int main()
{
	int* ret = NULL;
	int nums[] = { 5 }, target = 5;
	int * result = searchRange(nums,1, target, ret);
	 printf ("result[0]=%d,result[1]=%d",result[0],result[1]);
}