Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   Optimize binary serach... (http://www.go4expert.com/forums/optimize-binary-serach-t15876/)

asadullah.ansari 20Jan2009 10:48

Optimize binary serach...
 
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.

asadullah.ansari 20Jan2009 10:54

Re: Optimize binary serach...
 
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.

xpi0t0s 20Jan2009 16:47

Re: Optimize binary serach...
 
http://www.google.com/search?q=binary+search
The first hit is a Wiki article which probably explains everything you need to know.


All times are GMT +5.5. The time now is 05:28.