What is this?

[Fusion1]

Can some one please tell me what does this code fragment mean?

while (khi - klo > 1)
 {

	k = (khi + klo) >> 1;
	if (xa[k] > x) khi = k;
	else klo = k;

 }

[ResidentBiscuit]

while (khi - klo > 1) //Just a condition, also can be written as (khi > 1 + klo) if that helps
 {

	k = (khi + klo) >> 1; //The >> here is a bitshift operator. Look it up.
	if (xa[k] > x) khi = k; //Condition, if met khi = k
	else klo = k;  //If not met, klo = k

 }

It's pretty straightforward, except for the bit shift operator which might have thrown you off. The variables are also terrible named.

[ne555]

At the end, the index `klo' would point to the lower bound of the `x' element in the `xa' container.
It uses a binary search to do that.


Edit: No, that was wrong. `klo' does not point to the lower bound, that element could compare in any way to `x'.
But it could be used for a `member()' function

[Fusion1]

Thanks for the replies!
What is that bit shift operator?

[ne555]

http://en.wikipedia.org/wiki/Bitshift
In that case it would be equivalent to divide by 2. (khi+klo)/2

[mutexe]

I think it being all scrunched up makes it a little less clear as well.

while ( (khi - klo) > 1)
{
	k = (khi + klo) >> 1;

	if (xa[k] > x)
        {
            khi = k;
        }
	else
        {
            klo = k;
        }
 }

[JLBorges]

/* annotation: 
    in an ordered sequence xa[N] (array[N]), we want to
    search for the value x (searched_for_value).

    khi (pos_high) is initially the position of the largest element (N-1) 
    klow (pos_low) is initially the position of the smallest element (0) 
*/

// while (khi - klo > 1)
while( pos_high > pos_low )
{
    /* annotation: 
        searched_for_value, if present, 
        must be at a position in the range [ pos_low, pos_high ] 
    */

    // k = (khi + klo) >> 1;
    /* annotation: 
        compute the position of the middle element,
        the position that is equidistant from the low and high positions
    */
    pos_mid = ( pos_high + pos_low ) / 2 ;
    
    /* annotation: if at this point,
    if( array[pos_mid] == searched_for_value ) 
    {
        we have found searched_for_value
        we could return pos_mid as the position at which it was found;
    }
    
    else
    */
        
    // if (xa[k] > x) khi = k;
    /* annotation: 
        if the value in the middle is greater than searched_for_value,
        searched_for_value, if present, must be at a position in the range [ pos_low, pos_mid ]
    */
    if( array[pos_mid] > searched_for_value ) pos_high = pos_mid ;
    
    // else klo = k;
    /* annotation: 
        if the value in the middle is not greater than searched_for_value,
        searched_for_value, if present, must be at a position in the range [ pos_mid, pos_high ]
    */
    else pos_low = pos_mid ;
}

/* annotation: 
    at this point, pos_low == pos_high
    is the value at that position == searched_for_value ?
*/

[ne555]

> khi (pos_high) is initially the position of the largest element (N-1)
> while( pos_high > pos_low )
you changed the condition, originally it was a range [)

Taking your code, suppose
pos_low = 0
pos_high = 1
array[0] < searched_for_value

you've got an infinite loop

[JLBorges]

> you changed the condition, originally it was a range [)

Yes. Thank you.