# Great Example to Illustrate How to Write Correct Binary Search Code

• Simple idea,
Difficult to write correct code

Idea is simple:

1. find start index
2. find end index
3. return [start, end]

The Subtle Part:
How to define mid-point in binary search?
How to update two pointers?
What is the while loop condition?

``````public class Solution {
public int[] searchRange(int[] nums, int target) {
// both (i+j)/2 and (i+j)/2 + 1 could be interpreted as mid-point
// in (i+j)/2     as mid-point cases, use lo = mid+1, hi = mid to avoid infinite loop
// in (i+j)/2 + 1 as mid-point cases, use hi = mid-1, lo = mid to avoid infinite loop

// search for start point
int i = 0, j = nums.length-1;
while(i != j){
// loop invariant : start point must be in [i,j]
int mid = (i+j)/2;
if(nums[mid] >= target) j = mid;
else i = mid + 1;
}

int start = i;
if(nums[i] != target) return new int[]{-1,-1};

// search for end point
j = nums.length-1;
while(i != j){
// loop invariant : end point must be in [i,j]
int mid = (i+j)/2 + 1;
if(nums[mid] > target) j = mid-1;
else i = mid;
}

return new int[]{start, j};

}
}
``````

• @Jingshi very nice!

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