0

I am using binary search to search a number from a sorted array of numbers in O(log(n)) time. My C function for search is as follows:

search(int array[],int size,int search)
 {
 int first=0;
 int last=size-1;
 int middle = (first+last)/2;
   while( first <= last )
   {
      if ( array[middle] < search )
         first = middle + 1;    
      else if ( array[middle] == search ) 
      {
         printf("%d found at location %d.\n", search, middle+1);
         break;
      }
      else
         last = middle - 1;

      middle = (first + last)/2;
   }
   if ( first > last )
      printf("Not found! %d is not present in the list.\n", search);
}

Here size is the size of array and search is the number to search. Is there any way to perform the search in less complexity then the above program?

Jainendra
  • 24,713
  • 30
  • 122
  • 169
  • 1
    (1) `there must be a way` - why? (2) If your array is in RAM, in 32 bits systems, `log_2(n) < 32`. Is it that bad? (3) Are you looking for better asymptotic complexity [`Omega(logn)`] or an implementation with better constants? – amit Apr 27 '12 at 11:32
  • Standard C defines [`bsearch()`](http://pubs.opengroup.org/onlinepubs/9699919799/functions/bsearch.html) which searches the array in O(log(n)) time. I believe you can't do better with comparison based search. – pmg Apr 27 '12 at 11:33
  • All comparisons based algorithm have a lower bound of logn. @pmg proofs have been made to back up your belief. – UmNyobe Apr 27 '12 at 11:36
  • Possible duplicate of [this question](http://stackoverflow.com/q/4057258/1009831). – Evgeny Kluev Apr 27 '12 at 11:56
  • Possible duplicate of http://stackoverflow.com/questions/8565583/what-is-the-tight-lower-time-complexity-bound-for-searching-in-a-sorted-array as well. – Philip Apr 27 '12 at 12:18

1 Answers1

0

Yes, use a hash table. It should be faster in the average case.

James
  • 9,064
  • 3
  • 31
  • 49
  • 3
    which means it is not a sorted array anymore. – UmNyobe Apr 27 '12 at 11:38
  • 1
    @UmNyobe: You can store both, a sorted array **and** a `hashmap:key->index`. Correct me if I miss something, but I don't think it will make other sorted array ops assymptotically slower as well. I don't think it is a good solution, but it is possible. – amit Apr 27 '12 at 11:47
  • @amit yes. The OP should clarify more what he needs. I am not the downvoter though – UmNyobe Apr 27 '12 at 11:54