binary_eagle's blog

Binary Search over non-monotonic range.
By binary_eagle, 10 years ago, In English

Hi guys,

Can anyone share their ideas over searching over a non-monotonic range. Is there a way that the basic binary search implementation can be modified to handle non-monotonic ranges?

Please assist with your ideas and thought/techniques.

Thank you

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

In general you cannot deal with non-monotonic chunks of data faster than O(n) because you have to look at all N elements to be sure whether an element is presented or not, because you have absolutely no extra information. Even if you've checked N-1 elements, you know nothing about the remaining Nth.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you International Grandmaster Yeputons. But what if we have additional information that the data set is monotonic over some ranges. Let me illustrate

    [a..b] is the full range and is not monotonic a < x,y < b [x..y] is monotonic

    So i guess what am asking is that when we have monotonic ranges inside a bigger non-monotonic range and we have perfect information of the indexes, Can we intelligently search for data ?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Binsearch over each interval which may contain needle is resonable for you?

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can run a binary search on the monotonic piece, and if it fails, a linear search on what's left. Depending on the details of your problem, this may or may not result in a speedup.

      → Reply