Suppose we are given an array, A, of n nonintersecting segments, s 1 , s 2 ,...,s n , with endpoints on the lines y = 0 and y = 1, and ordered from left to right. Given a point q with 0 < y(q) < 1, design an algorithm that in O(log n) time computes the segment s i
Chapter 22, Creativity #14
Suppose we are given an array, A, of n nonintersecting segments, s1, s2,...,sn, with endpoints on the lines y = 0 and y = 1, and ordered from left to right. Given a point q with 0 < y(q) < 1, design an algorithm that in O(log n) time computes the segment si of A immediately to right of q, or reports that q is to the right of all the segments.
This problem has been solved!
Do you need an answer to a question different from the above? Ask your question!
Answer
We can use a binary search to locate q. The important observation is that the segments in A are ordered left to right. So, given any segment si in A, we can in constant time determine whether q is to the left or right of si , which in turn determines if we should continue searching among the segments to the left or right of si . Thus, we can ultimately locate the segment …View the full answer
Related Book For 
Algorithm Design And Applications
1st Edition
Authors: Michael T. Goodrich, Roberto Tamassia
ISBN: 9781118335918