Search For A Range

2151 단어
public class Solution {
    public int[] searchRange(int[] A, int target) {
		// Start typing your Java solution below
		// DO NOT write main() function
		int[] res = {-1, -1};
		if(A.length == 0)
			return res;
		int begin = 0;
		int end = A.length - 1;
		while(begin < end){
			int mid = begin + (end - begin) / 2;
			if(A[mid] >= target)
				end = mid;
			else
				begin = mid + 1;
		}
		if(A[begin] != target)
			return res;
		else
			res[0] = begin;
		
		begin = 0;
		end = A.length - 1;
		while(begin < end){
			int mid = begin + (end - begin + 1) / 2;// pay attention to +1 here, eg. {0, 1, 2, 3}, +1 makes mid to 2, not 1.
			if(A[mid] <= target)
				begin = mid;
			else
				end = mid - 1;
		}
		if(A[end] != target)
			return res;
		else
			res[1] = end;
		
		return res;
	}
}

Recursive:
	public int[] searchRange(int A[], int n, int target) {
		// Start typing your JAVA solution below
		// DO NOT write int main() function
		int[] result = {-1, -1};
		result[0] = findPosition(A, 0, n - 1, target, true);
		result[1] = findPosition(A, 0, n - 1, target, false);
		return result;

	}

	int findPosition(int A[], int begin, int end, int target, boolean leftFlag) {
		if (begin > end)
			return -1;
		int middle = (begin + end) / 2;
		if (A[middle] == target) {
			int position;
			if (leftFlag) {
				position = findPosition(A, begin, middle - 1, target, leftFlag);
			} else {
				position = findPosition(A, middle + 1, end, target, leftFlag);
			}
			return (position == -1) ? middle : position;
		} else if (A[middle] < target) {
			return findPosition(A, middle + 1, end, target, leftFlag);
		} else {
			return findPosition(A, begin, middle - 1, target, leftFlag);
		}
	}

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] .

좋은 웹페이지 즐겨찾기