# My accept Java solution using Binary Search. Wonder any good suggestion?

• Thank you for pointing out that my solution in fact takes O(n)

The idea is that,

1. First use Binary search to search a given target value.
2. Then check its left side and right side, to see whether its duplicates exist.

But I think my recursion function includes to many parameters, would this impact my performance? Could anyone give me some good advice about my solution to relieve this situation?

``````  public int[] searchRange(int[] A, int target) {
int left = 0;
int right = A.length - 1;
int[] result = new int[2];

_binarySearch(A, target, left, right, result);
return result;
}

// recursive function
public void _binarySearch(int [] A, int target, int left, int right, int[] result){
// not exist
if(left>right){

result[0] = -1;
result[1] = -1;
return;

}
int mid = left + (right - left)/2;
if(target == A[mid]){
int start = mid;
int end = mid;
// check left side duplicates
while(start > 0){
if(A[start - 1] == target)
start--;
else{
break;
}
}
// right side duplicates
while(end < A.length - 1){
if(A[end + 1] == target)
end++;
else{
break;
}
}

result[0] = start;
result[1] = end;

}
// on left side
else if(target < A[mid]){
_binarySearch(A, target, left, mid - 1, result);
}
// right side
else if(target > A[mid]){
_binarySearch(A, target, mid + 1, right, result);
}
}``````

• suppose the input array is 2 2 2 2 .......(many 2s), for your algorithm, the run time will be O(n) which is the worst case, but not O(logn).

when we find the target value `A[mid] == target`, we can continue using binary search to find the left or right bound, but before that, check whether it already reached the left/right bound (for left bound: `if (mid == 0)` or `if (A[mid - 1] != target)`).

for the implementation, more lines needed as we find the target in the array, need to check `A[i - 1]` and `A[i + 1]`, so define the methods separately. For the worst case, it is still O(logn)

here is my solution:

``````public class Solution {
public int[] searchRange(int[] A, int target) {
int[] arr = new int[2];
arr[0] = searchLeft(A, target);
arr[1] = searchRight(A, target);
return arr;
}

private int searchLeft(int[] A, int target) {
int s = 0, e = A.length - 1;
while (s <= e) {
int mid = s + (e - s) / 2;
if (A[mid] == target) {
if (mid == 0) {
return mid;
}
if (A[mid - 1] == target) {
e = mid - 1;
} else {
return mid;
}
} else if (target > A[mid]) {
s = mid + 1;
} else {
e = mid - 1;
}
}
return -1;
}
private int searchRight(int[] A, int target) {
int s = 0, e = A.length - 1;
while (s <= e) {
int mid = s + (e - s) / 2;
if (A[mid] == target) {
if (mid == A.length - 1) {
return mid;
}
if (A[mid + 1] == target) {
s = mid + 1;
} else {
return mid;
}
} else if (target > A[mid]) {
s = mid + 1;
} else {
e = mid - 1;
}
}
return -1;
}
}
``````

the runtime is actually O(2*logn) as we need to search left & right separately

• Oh, really excellent solution!

My solution only guarantee best case O(log(n))

Thank you! Benefit a lot!

• yeah, for the array without duplicate numbers, your sol will be O(logn).

thanks!

• you don't need to define a global variable s,e,mid.yes?

• Yeah, I think so

• My solution uses a similar idea. A small modification is that I use binary search to check the left bound and right bound.

``````public int[] searchRange(int[] A, int target) {
if(A==null)
return new int[]{-1,-1};
int l = 0,r = A.length-1,m;
while(l<=r)
{
m = (l+r)/2;
if(target<A[m])
r = m - 1;
else if(target>A[m])
l = m + 1;
else {
int mt = m, mm;
while(mt<r-1)
{
mm = (mt+r)/2;
if(A[mm]>target)
r = mm;
else
mt = mm;
}
if(A[r]>target)
r--;
mt = m;
while(l<mt-1)
{
mm = (l+mt)/2;
if(A[mm]<target)
l = mm;
else
mt = mm;
}
if(A[l]<target)
l++;
return new int[]{l,r};
}
}
return new int[]{-1,-1};
}
``````

• My solution looks for left and right bounds using binary search. It is O(log(N)). I think it is very easy to understand.

``````public class Solution {
public int[] searchRange(int[] a, int target) {
int l = searchRangeLeft(a, target);
if(l == -1)
return new int[] {-1, -1};

int r = searchRangeRight(a, target);

return new int[] {l, r};
}

private int searchRangeLeft(int[] a, int target) {
int l = 0;
int r = a.length-1;
while (r-l > 1) {
int m = l + (r-l)/2;
if(a[m] < target) {
l = m;
}
else if(target <= a[m]) {
r = m;
}
}

if(a[l] == target)
return l;
else if(a[r] == target)
return r;
else
return -1;
}

private int searchRangeRight(int[] a, int target) {
int l = 0;
int r = a.length-1;
while (r-l > 1) {
int m = l + (r-l)/2;
if(a[m] <= target) {
l = m;
}
else if(target < a[m]) {
r = m;
}
}

if(a[r] == target)
return r;
else if(a[l] == target)
return l;
else
return -1;
}
}``````

• My code, idea is same with others.

``````public class Solution
{
private int searchLeft(final int[] A, final int target)
{
int left = 0;
for (int right = A.length - 1; left <= right; )
{
final int middle = (left + right) / 2;
if (A[middle] >= target)
{
right = middle - 1;
}
else
{
left = middle + 1;
}
}

return (left >= A.length || A[left] != target) ? -1 : left;
}

private int searchRight(final int[] A, final int target)
{
int right = A.length - 1;
for (int left = 0; left <= right; )
{
final int middle = (left + right) / 2;
if (A[middle] <= target)
{
left = middle + 1;
}
else
{
right = middle - 1;
}
}

return (right < 0 || A[right] != target) ? -1 : right;
}
public int[] searchRange(int[] A, int target)
{
final int[] result = new int[2];
final int left = searchLeft(A, target);
if (-1 == left)
{
result[0] = result[1] = -1;
}
else if (A.length - 1 == left)
{
result[0] = result[1] = left;
}
else
{
result[0] = left;
result[1] = searchRight(A, target);
}

return result;
}
}``````

• Mine with similar idea.

``````public class Solution {
public int[] searchRange(int[] A, int target) {
int[] result = new int[2];
int start = 0;
int end = A.length - 1;
result[0] = result[1] = -1;
while(start <= end && ((result[0] == -1) || (result[1] == -1))) {
if(A[start] == target && result[0] == -1) {
result[0] = start;
}
if(A[end] == target && result[1] == -1) {
result[1] = end;
}
int middle = (start + end) / 2;
if(A[middle] < target) {
start = middle + 1;
}
else if(A[middle] > target) {
end = middle - 1;
}
else {
if(result[0] == -1) {
start++;
}
if(result[1] == -1) {
end--;
}
}
}
return result;
}
}``````

• same idea, but when we know the left is not -1, we know the start for search right is left, at the same time, the right can not be return -1(it must be exist), the search for right can be simpler.

``````   public int[] searchRange(int[] A, int target) {

if (A == null || A.length == 0) {
return new int[] { -1, -1 };
}
int start = start(A, target);
if (start == -1) {
return new int[] { -1, -1 };
}

int end = end(A, start, A.length - 1, target);
return new int[] { start, end };
}

private int start(int A[], int target) {
int start = 0;
int end = A.length - 1;
while (start <= end) {
if (start == end && A[start] == target) {
return start;
}

int mid = (start + end) / 2;
if (A[mid] > target) {
end = mid - 1;
continue;
}
if (A[mid] < target) {
start = mid + 1;
continue;
}
end = mid;
}

return -1;
}

private int end(int A[], int start, int end, int target) {
while (true) {
if (start == end) {
return start;
}
int mid = (start + end + 1) / 2;
if (A[mid] > target) {
end = mid - 1;
continue;
}
start = mid;
}
}``````

• ``````public int[] searchRange(int[] A, int target) {
int i = 0, j = A.length-1;
int left = -1, right = -1;
int mid = 0;
//judge if the target exists or not
while(i <= j){
mid = i + ((j-i)>>1);
if(A[mid] == target)
break;
else if(A[mid]>target)
j = mid - 1;
else i = mid + 1;
}
//if target is not in the array
if(A[mid] != target)	return new int[]{-1,-1};
//search the left indice
i = 0;j = mid -1;
while(i <= j){
mid = i + ((j-i)>>1);
if(A[mid] == target)
j = mid - 1;
else i = mid + 1;
}
left = i;
//find the right indice
i = mid+1;j = A.length -1;
while(i <= j){
mid = i + ((j-i)>>1);
if(A[mid] == target)
i = mid + 1;
else j = mid - 1;
}
right = j;
return new int[]{left,right};
}``````

• There's no need for two versions of binary search: for right bound just search for [target+1] and shift one position to the left.

``````public class Solution {
public int[] searchRange(int[] nums, int target) {

// 1. Search for the left bound
int left = binarySearch(nums, target);

// 2. No target found -- return
if (left >= nums.length || nums[left] != target)
return new int[] {-1, -1};

// 3. Search for the right bound
int right = binarySearch(nums, target + 1) - 1;
return new int[] { left, right };
}

/* Returns index of first target if found or
index of the first element larger than target */
private int binarySearch(int[] nums, int target) {
int lo = 0;
int hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] < target)
lo = mid + 1;
else
hi = mid - 1;
}
return lo;
}
}``````

• Please see my explanation here

• this is my solution, i thing it takes O(logn) times too but more than 2 * logn.

``````var searchRange = function(nums, target) {

var result = [-1, -1];
var binarysearch = function findTarget(A, l, h, target) {

if (l > h) {
return -1;
}
var mid =(h + l)/2;
var mid =  Math.floor(mid)
if (A[mid] === target) {
return mid;
}
if (target < A[mid]) {
return findTarget(A, l , mid-1, target);
}else {
return findTarget(A, mid+1, h, target);
}
}

var res = binarysearch(nums, 0, nums.length - 1, target);
console.log(res);
if (res === -1) {
return [-1, -1];
}else {
var left = res;
var right = res;
while (left > -1) {
result[0] = left;
left = binarysearch(nums, 0, left - 1, target);
}
while (right > -1) {
result[1] = right;
right = binarysearch(nums, right + 1, nums.length - 1 , target);
}
return result;
}
``````

};`

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.