public class Solution {
public int[] searchRange(int[] A, int target) {
int start = Solution.firstGreaterEqual(A, target);
if (start == A.length  A[start] != target) {
return new int[]{1, 1};
}
return new int[]{start, Solution.firstGreaterEqual(A, target + 1)  1};
}
//find the first number that is greater than or equal to target.
//could return A.length if target is greater than A[A.length1].
//actually this is the same as lower_bound in C++ STL.
private static int firstGreaterEqual(int[] A, int target) {
int low = 0, high = A.length;
while (low < high) {
int mid = low + ((high  low) >> 1);
//low <= mid < high
if (A[mid] < target) {
low = mid + 1;
} else {
//should not be mid1 when A[mid]==target.
//could be mid even if A[mid]>target because mid<high.
high = mid;
}
}
return low;
}
}
A very simple Java solution, with only one binary search algorithm


One Pass O(logn) Binary Search Solution No Helper, based on your idea with some improvement.
public int[] searchRange(int[] nums, int target) { int min = 1; int max = 1; int[] ret = {1,1}; int l = 0; int r = nums.length 1; int mid = (l + r) /2; if(l > r)//where left surpass right, which means no elements left in the array return ret; if(nums[mid] == target){//once target is hit, search its left sub array, and right right sub array to find the left most target, and right most target min = mid; max = mid; int[] newleft = Arrays.copyOfRange(nums, 0, mid);//inclusive, exclusive int[] newright = Arrays.copyOfRange(nums, mid + 1, nums.length); ret = searchRange(newleft,target); if(ret[0] != 1) min = ret[0];//update min if target is hit in the left sub array ret = searchRange(newright,target); if(ret[1] != 1) max = mid + 1 + ret[1];// update max if the target is hit, meanwhile adjust index to the original array return new int[]{min,max}; }else if(nums[mid] > target){ // search left int[] newleft = Arrays.copyOfRange(nums, 0, mid);//inclusive, exclusive return searchRange(newleft,target); }else if(nums[mid] < target){// search right int[] newright = Arrays.copyOfRange(nums, mid + 1, nums.length); ret = searchRange(newright,target); if(ret[1] != 1){//adjust left most right index to the original array ret[1] = ret[1] + mid + 1; } if(ret[0] != 1){ ret[0] = ret[0] + mid + 1; //adjust left most target index to the original array } return ret; } return ret; }

Here is a better one:
https://leetcode.com/discuss/69621/simplestfastestandnonrecursivejavasolution

Well, to be frank, I don't see an improvement in your code. It is actually even slower than the original one because you are copying the array several times, which is time consuming. To be precise, your algorithm is of time O(n) rather than O(log n) because copying an array is of O(n).

Hello @lhai, this is a trick of preventing possible overflow. Imagine a case where
low = Integer.MAX_VALUE  10, high = Integer.MAX_VALUE  5

@kxcf
I always wonder when we set high equal to A.length or A.length1. Could anyone please provide some explanation? Thank you!

Slight optimization, if you pass in high and low into the helper method as parameters then at line 7 you can pass in start as the new low. Would save you log(n) iterations in the helper for the worse case of target being all the way to the right.
target = 10
[1,1,1,1,1,1,1,1,1...................a lot of 1's...................10,11]

@jun711
Yes, I was wondering about the same question:high = A.length
vshigh = A.length1

I think it's for the case in which there is only one element.
For example, in the test case: [1] 1
If you usehigh = A.length  1;
high will be 0 (11)
This makeswhile (low < high) false.
So every time you call firstGreaterEqual(), it will return 0 directly.
Thus,return new int[]{start, Solution.firstGreaterEqual(A, target + 1)  1};
will return {0, 1}, which is incorrect.


@kxcf If target+1 is not in the array, then the right end of the range should be firstGreaterEqual(A, target + 1). Is this right?

@cutezgh said in A very simple Java solution, with only one binary search algorithm:
@kxcf If target+1 is not in the array, then the right end of the range should be firstGreaterEqual(A, target + 1). Is this right?
Never mind. Your firstGreaterEqual finds the left end of the range if the target exists, and the first number greater than the target if it doesn't exist. Basically, high = n (not n1) is important.

My python solution is similar :)
class Solution(object): def searchRange(self, nums, target): def BinSearch(arr,x): l=0 r=len(arr)1 while l<=r: mid=(l+r)/2 if arr[mid]<x: l=mid+1 else: r=mid1 return l if not nums: return [1,1] start=BinSearch(nums,target) end=BinSearch(nums,target+1)1 if start<=end: return [start,end] else: return [1,1] #87 / 87 test cases passed. #Status: Accepted #Runtime: 38 ms

public class Solution {
public int[] searchRange(int[] nums, int target) {
int lo = 0;
int hi = nums.length 1;
int rh = 1;
int rl = 1;while(lo<=hi){ int mid = (lo+hi)/2; if(target == nums[mid]){ rl = focc(lo,mid,target,nums); rh = locc(mid,hi,target,nums); break; } else if(target<nums[mid]) hi = mid1; else lo = mid+1; } int[] a = new int[2]; a[0] = rl; a[1] = rh; return a; } int focc(int lo,int hi,int t,int[] n){ while(lo<=hi){ int m = (lo+hi)/2; if(t==n[m]){ if(m==lo  n[m1]<t) return m; else hi = m1; } else lo = m+1; } return 1; } int locc(int lo,int hi,int t,int[] n){ while(lo<=hi){ int m = (lo+hi)/2; if(t==n[m]){ if(m==hi  n[m+1]>t) return m; else lo = m+1; } else hi = m1; } return 1; }
}
This is my solution.. can someone help me figure out its complexity and is it more time consuming than the one posted?

@kxcf great! Thanks for sharing!!!
public class Solution { public int[] searchRange(int[] nums, int target) { if(nums==null  nums.length<1){ return new int[]{1,1}; } int start=searchBinary(nums,target); if(start==nums.length  nums[start]!=target){ return new int[]{1,1}; } int end = searchBinary(nums,target+1); return new int[]{start,end1}; } public int searchBinary(int[] nums,int target){ int i=0; int j=nums.length; while(i<j){ int mid=(i+j)>>>1; if(nums[mid]<target){ i=mid+1; }else{ j=mid; } } return i; } }