Question

In Java, if I have two intervals....interval A (1-5) and interval B (3-10)...how can i effectively use binary search to not only show the intervals but to also show the overlap which in this case is (3-5).

Answer 1

You can do this by modified versio of binary search

Let interval is [x, y]

1) Use Binary search to get index of the first occurrence of x in arr[]. Let the index of the first occurrence be i.
2) Use Binary search to get index of the last occurrence of y in arr[]. Let the index of the last occurrence be j.
3) Return (j – i + 1);

For finding overlap:

Let two interval [x,y] and [p,q]

if p < x and q > y

return [x,y]

if p < x and q < y

return [x,q]

if p > x and p > y

No overlap

if p > x and p < y:

return [p,y]

// Please comment if this is what you are not looking for with details. I will update answer accordingly.