Title:
Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return
.
- [-1, -1]
For example,
Given
and target value 8, return
- [5, 7, 7, 8, 8, 10]
.
- [3, 4]
这道题给定一个排序好的数组,然后找到重复的数字,并输出序号即可。
该题的要求是时间复杂度为O(log n),也就是说不能采用从头遍历到尾的方法,容易超时。因此采用另一种做法,从两边同时向中间靠拢。由于是排序好的数组,因此判断逻辑较为简单。
Solution:
- int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
- int *result=(int*)malloc(sizeof(int)*2);
- int i,j;
- int tmp;
- if (numsSize<=0) {
- *returnSize=2;
- result[0]=-1;
- result[1]=-1;
- return result;
- }
- if (numsSize==1) {
- if (target==nums[0]) {
- *returnSize=2;
- result[0]=0;
- result[1]=0;
- return result;
- }
- else {
- *returnSize=2;
- result[0]=-1;
- result[1]=-1;
- return result;
- }
- }
- i=0;
- j=numsSize-1;
- while(i<j) {
- if (target<nums[i] || target>nums[j]){
- *returnSize=2;
- result[0]=-1;
- result[1]=-1;
- return result;
- }
- else if (target==nums[i]) {
- tmp=i+1;
- while(tmp<numsSize && nums[tmp]==nums[i]) {
- tmp++;
- }
- *returnSize=2;
- result[0]=i;
- result[1]=tmp-1;
- return result;
- }
- else if (target==nums[j]) {
- tmp=j-1;
- while(tmp>=0 && nums[tmp]==nums[j]) {
- tmp--;
- }
- *returnSize=2;
- result[0]=tmp+1;
- result[1]=j;
- return result;
- }
- else {
- if (i+1==j-1)
- i++;
- else {
- i++;
- j--;
- }
- }
- }
- *returnSize=2;
- result[0]=-1;
- result[1]=-1;
- return result;
- }
来源: http://blog.csdn.net/hahachenchen789/article/details/78092490