1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Optimize binary serach...

Discussion in 'C' started by asadullah.ansari, Jan 20, 2009.

  1. asadullah.ansari

    asadullah.ansari TechCake

    Joined:
    Jan 9, 2008
    Messages:
    356
    Likes Received:
    14
    Trophy Points:
    0
    Occupation:
    Developer
    Location:
    NOIDA
    All of you alraedy know the binary search..I need not to explain that algorithm...
    we know that there are two compariosions one for greater than mid value and other is for less than mid value. Optimize this algorithm/program so that only one comparision shoul happened in that algorithm?


    Note: binary search means not a binary serch tree.... BST algorithm is totally different that Binary Serch algorithm.
     
  2. asadullah.ansari

    asadullah.ansari TechCake

    Joined:
    Jan 9, 2008
    Messages:
    356
    Likes Received:
    14
    Trophy Points:
    0
    Occupation:
    Developer
    Location:
    NOIDA
    Now i want to make this problem more clear...
    binary serach algo is as:
    Code:
       BinarySearch(A[0..N-1], value) {
           low = 0
           high = N - 1
           while (low <= high) {
               mid = (low + high) / 2
               if (A[mid] > value)             ///First check
                   high = mid - 1
               else if (A[mid] < value)       //second check
                   low = mid + 1
               else
                   return mid // found
           }
           return -1 // not found
       }
    In a while loop there is two check(if condition) ...You have to reduce it by one inside while loop.
     
    Last edited by a moderator: Jan 20, 2009
  3. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England

Share This Page