Search for a Range

Given a sorted array of integers, 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 [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

基本思路：

题目意思就是给定一个有序数组，然后给定一个目标数，在数组中查找目标数的起始范围，若没有找到则返回[-1,-1]。本题利用二分查找目标数，然后两边查找。

   	public int[] searchRange(int[] A, int target)
	{
		int[] result = new int[2];
		int index;
		int start = 0;
		int end = 0;
		int temp1,temp2;
		index = search(A, 0, A.length-1, target);
		if(index==-1)
		{
			result[0]=-1;
			result[1]=-1;
		}
		else
		{
			temp1 = index-1;
			while(temp1>=0)
			{
				if(A[temp1]!=target)
				{
					start = temp1+1;
					break;
				}
				temp1--;
			}
			temp2 = index+1;
			while(temp2<A.length)
			{
				if(A[temp2]!=target)
				{
					end = temp2-1;
					break;
				}
				temp2++;
			}
			if(temp1<0)
				start=0;	
			if(temp2>=A.length)
				end = A.length-1;
			result[0]=start;
			result[1]=end;
		}
		return result;
	}
	
	public int search(int[] A , int low , int high,int target)
	{
		if(low>high)
			return -1;
		int mid = (low+high)/2;
		if(target == A[mid])
			return mid;
		else if(target>A[mid])
			return search(A, mid+1, high, target);
		else
			return search(A, low, mid-1, target);
	}

Search for a Range,布布扣,bubuko.com

Search for a Range

原文：http://blog.csdn.net/cow__sky/article/details/19964165