Search for a Range (Java)

Leetcode

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

Solution: because of O(logn), so we should consider about binary search, so how to apply binary search to find the low bound and high bound? We can make target -0.5 for searching low bound and target+0. 5 for the high bound. Be careful the corner case

	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].
	Time complexity: O(logn)
	public class Solution {
	public int[] searchRange(int[] A, int target) {
	if (A==null) return null;
	int[] result={-1,-1};
	int low=binarySearch(A,target-0.5);
	// Be care for there , low>=A.length must be check first or
	// there may be a out of boundary exception cause
	// the binarySearch function in this question return low instead of null
	// if the target are not in the array
	if (low>=A.length||A[low]!=target){
	return result;
	}
	result[0]=low;
	result[1]=binarySearch(A,target+0.5)-1;
	return result;
	}
	public int binarySearch(int[] A, double t){
	int low = 0, high = A.length - 1;
	while(low <= high){
	int m = (low + high) / 2;
	if(A[m] == t) return m;
	if(A[m] > t) high = m - 1;
	else low = m + 1;
	}
	return low;
	}
	}

view raw Search for a Range.java hosted with ❤ by GitHub