saanc's blog

Binary Search
By saanc, 10 years ago, In English

Do you want to know about Binary Search? Do you want a right place to learn it? Open the link given below and get a right place :) My second blog post: http://sanugupta.wordpress.com/2014/06/05/linear-search-vs-binary-search/

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

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

I think the common problem of most of binary search tutorials for beginners that I've seen is that they never go any further than searching for a number in the array. Given you understood that you might still encounter problems in understanding how to apply binary search to solve many other problems like this — 378D - Preparing for the Contest — where there is some monotonic function instead of an explicitly built sorted array.

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

    You are right brother! I accept your suggestion. But think of one thing: you can't go beyond the scope of the beginners... Suppose if you are a beginner then first of all you prefer to learn a concept completely rather than its variation.

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

      Learning it completely means being able to solve variations of this problem.

      → Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

One thing which is very important for beginners is the fact that binary search is applicable in many situations where there is mathematical solution. And very often it is much faster to code — instead of solving for mathematical direct equation you just create function which calculates amount needed and do binary search. You would probably not do that in production code, but in competitive programming factor of log(n) added by binary search is often irrelevant, while speed of coding is extremely important.

My own experience: Problem: Bullseye from GCJ.

At that time I had just finished prof Sedgewicks course about Analytical Combinatorics, so I was very proud that after drawing formulas for 15 minutes I came up with closed form solution for the problem. I was not so happy when I discovered that:\

  • closed-form solution suffered from need to take sqrt from very big numbers. I was able to overcome that.

  • solution without any closed form formulas, using simple binary search, can be coded in 3-5 minutes.

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

    You guys are very helpful. your suggestions are great. I am going to write and other post on binary search next which deals with other variations of it.

    → Reply