Binary Search

Why don't you use the built in function (bsearch)?

Axter>       Why don't you use the built in function (bsearch)?

bsearch returns a pointer to an occurrence of key in the array pointed to by base. If key is not found, the function returns NULL.

That means bsearch doesn't give me the position for inserting a new number .

>>> glebspy

Could you check again ? Maybe, that code has problem with

case 1 :
   SortedArray[] = { 1, 3 }
   numEle = 2
   target = 2

case 2 :
   SortedArray[] = {  1 }
   numEle = 1
   target = 3
   

Thank for helping .

  Hi, all!
   For glebspy: your code still has a little math problem:

current_Divider =
       current_Lower_Bound + current_Range/2;  // ?!?!?

    That's hardly the middle of the interval. I'm sure you didn't check close enough, and I'm sure you meant:
     
current_Divider =
       (current_Lower_Bound + current_Range) / 2;  

    And another thing:
    Even if the search is O( lg2 n ), I'm sure you all know adding the number in the array, is a completely different story. Now, if you were to use a binary three...

Sorry, my mistake, I didn't check close enough.
I ussually do this

(current_Lower_Bound + current_Upper_Bound) / 2;

so that's why a wrote the above.

Sorry glebspy.

But the last comment still stands.

int binarysearch(int x[]/* input array */, int n /* no of elements */, int t /* key */)
{     int l, u, m;
     l = -1;
     u = n;
     while (l+1 != u) {
          m = (l + u) / 2;
          if (x[m] < t)
               l = m;
          else
               u = m;
     }
     /* if (u >= n || x[u] != t)
          return -1;
        */
     return u; /* return position */
}

The original code returns -1 if the key is not found. Since you need the position at which the key is to be inserted even if it is not found, simply get back the upper bound at which the search terminated. This is the position where you insert the key.

You should still be able to use the built-in STD functions for this.

Try the following:

template<typename T>
size_t FindInsertionPoint(const T* Begin, const T* End, const T& Value)
{
     const T* i = std::upper_bound(Begin, End, Value);
     return i-Begin;
}

Example:

template<typename T>
size_t FindInsertionPoint(const T* Begin, const T* End, const T& Value)
{
     const T* i = std::upper_bound(Begin, End, Value);
     return i-Begin;
}

int main(int argc, char* argv[])
{
     int A[12] = {1, 5, 6, 6, 7, 9, 9, 9, 12, 17, 17, 20};
     
     int xi9 = FindInsertionPoint(&A[0], &A[sizeof(A)/sizeof(int)], 9);
     int xi12 = FindInsertionPoint(&A[0], &A[sizeof(A)/sizeof(int)], 12);
     int xi15 = FindInsertionPoint(&A[0], &A[sizeof(A)/sizeof(int)], 15);
     int xi0 = FindInsertionPoint(&A[0], &A[sizeof(A)/sizeof(int)], 0);
     int xi20 = FindInsertionPoint(&A[0], &A[sizeof(A)/sizeof(int)], 20);
     int xi21 = FindInsertionPoint(&A[0], &A[sizeof(A)/sizeof(int)], 21);
     int xi22 = FindInsertionPoint(&A[0], &A[sizeof(A)/sizeof(int)], 22);

     return 0;
}

  Hi, Thienpnguyen!
   OK, I just have one question for you, and for you all, correct me if I'm wrong:
   After you find the insertion point, given that you use an array, won't the actual insertion still be O(n)? ... because you will have to shift with one position all the remaining values.

   So, instead (aside from the binary search algorithm), which is excellent just for a search, when you actually want to add a value, won't this be better:
  (I presumed the array sorted ascending)

int InsertInSortedArray(int *SortedArray, int nE, int v)
{
 int i;
 for( i=nE; (i>0) && (SortedArray[i-1] > v) ; i--)
       SortedArray[i] = SortedArray[i-1];
 SortedArray[i] = v;
 return i;
}

What do you think?

int bsearch(int *array, int size, int target)
{
  int bottom = 0;
  int top = size;

  while (top > bottom)
  {
    int middle = (top + bottom) / 2;

    if (target == array[middle])
      return middle;

    if (target < array[middle])
      top= middle -1;
    else
      bottom= middle + 1;
  }

  return -1;   // not found
}

Whooops!!

>> while (top > bottom)

should be

>> while (top >= bottom)

MFCRich,
Your function could be done with the built-in library functions with less code, and made more generic.

Example:

template<typename T>
size_t MFCRich_bsearch(const T* Begin, size_t size, const T& target)
{
    const T* i = std::upper_bound(Begin, Begin+size, target);
     if (i = Begin+size) return -1;
    return i-Begin;
}

The question was about the binary search algorithm and I think my code demonstrates it.

>>The question was about the binary search algorithm and I
>>think my code demonstrates it.
I understand, but what I'm trying to point out, is that the built-in STL functions can do binanry search.

I'm trying to point out to everyone here that there's no need to reinvent the wheel.  Just use the built-in C++ functions.

Please look into the following piece of source, I may replicate the previous comments:

/*Binary search */

int bsearch( int key, int N, int* r )
{
     unsigned int i,high,low;

        if( N == 0 ) return 0;

     for ( low=0, high=N-1; high >= low ; )
     {
          i = (high+low) / 2;
          if ( key == r[i] )
               return( i );
          else if(key < r[i] )
               high = i-1;
          else
               low  = i+1;
     }
     return( -1 );
}

thienpnguyen,
Are you still there?

I think Robalitoru has a point, the real problem is to insert the new number into the correct position.
The code he suggested will do it in best time O(n) and with binary search O(log(n))+O(n)

mbenassor,
>>The code he suggested will do it in best time O(n) and
>>with binary search O(log(n))+O(n)

The code he suggested is NOT the best time.  A binary search is much faster.

mbenassor,
I don't think you understand how a binary search works.
At worse time, a binary search can find an item in a list of 1024, by performing 12 hits.
Compare that to a Sequential-Search, which at worse time can find an item in a list of 1024, by performing 1024 hits.

The difference between a Sequential-Search and a binary search increases exponentially.
For example, a list of 16,777,216 at worse time with a binary search only requires 26 hits.
With a Sequential-Search, the worse time is 16,777,216.

A Sequential-Search can not compare in speed to a Binary Search.

Axter I understand how a binary search works

Did you read the q. of thienpnguyen ?

"Assume I have a sorted array of integer numbers. Now I add a integer number into that array such that
it still is in order after adding number ."


He wants to INSERT a number into a sorted array - you can search and find the correct position in log(n) time but how can you ADD the new number to that position without the need to shift all the following numbers ?!?!
This is not a linked list, the array is allocated in a continues memory block and the time of the insertion is LINEAR.

Think about it.

I guess we were talking apples and oranges.
I was referring to the search routine, and I didn't realize that you were referring to the insertion mechanism.

I agree, that the insertion is linear, but IMHO the questioner is asking about the search algorithm, and not the insertion mechanism.

I assume that thienpnguyen knows that the insertion will be LINEAR and is only worried about having an optimized search routine.

Other then changing the array to a link list, there's not much you can do about the linear insertion.
You can however speed up the search by using the built-in binary search functions.

You can also make use of the built-in functions for the insertion routine, wish will also work faster then previous insertion functions post here.

Sorry experts, I will come back to work in next week.
At that time, I will decide what is the best comment .

Thank for helping .