Binary search loop is not breaking when the search element input is not prsenting in the sorted array

Question

I am implementing the binary search in C as below, but when I'm passing the element which is not available in the sorted array, the code is enter into infinite loop since the midelement is repetitively calculating the same value (midelement is 4, and then start index becomes 5 (elementtofind > InputArray[midelement]), end index is 4, hence again returns the mid element as 4) after the 9th iteration of the loop, can anyone find how could I improve this logic.

#define MAX_NUM_INPUT     (358U)
uint16 InputArray[MAX_NUM_INPUT] = {0x0103, 0x0104, 0x0109, 0x010A, 0x0133, 0x0180, 0x181, 0x183,.....upto 358 elements};

int main()
{
    boolean elmntFound = 0;
    uint16 elmntTofnd = 0x0134;
    elmntFound = SearchPassedElement(0, MAX_NUM_INPUT, elmntTofnd);
    if(elmntFound == 0)
    {
        printf("elementfound");
    }
    else
    {
        printf("elementNOTfound");
    }
}
static boolean SearchPassedElement (uint16 FrstElmntIdx,uint16 LstElmntIdx, uint16 ElmntToFind)
{
  boolean ReturnValue = 1;
  uint16 startIdx = FrstElmntIdx;
  uint16 endIdx = LstElmntIdx;
  uint16 loc_midElmntIdx;
  boolean OperationStatus = FALSE;
  
    if(LstElmntIdx >= FrstElmntIdx)
    {
        while (OperationStatus == FALSE)
        {
            loc_midElmntIdx = (startIdx + endIdx) / 2U ;
            if (ElmntToFind == InputArray[loc_midElmntIdx])
            {
                OperationStatus = TRUE;
                ReturnValue   = 0 ; 
            }
            else if (ElmntToFind > InputArray[loc_midElmntIdx])
            {
                /* if entire array was already checked*/
                if (startIdx == endIdx) 
                {  
                    OperationStatus = TRUE;
                    ReturnValue   = 1 ; 
                }
                else /* othewise, */
                {
                    startIdx = loc_midElmntIdx + 1U;
                }
            }
            else
            {
                /* if entire array was already checked*/
                if (startIdx == endIdx) 
                {  
                    OperationStatus = TRUE;
                    ReturnValue   = 1 ; 
                }
                else /* othewise, */
                {
                    endIdx = loc_midElmIdx - 1U ;
                }
            }
        }
    }
    else 
    {
        loopCntr = 0;
        /* Incorrect input arguments */
        ReturnValue = 1;
    }
    return ReturnValue;
}

I have found one logic as if the midelemnt is returned with same value for more than 3 times the lop shall be breaked, and evaluating the same.

static boolean SearchPassedElement (uint16 FrstElmntIdx,uint16 LstElmntIdx, uint16 ElmntToFind)
{
    boolean ReturnValue = 1;
    uint16 startIdx = FrstElmntIdx;
    uint16 endIdx = LstElmntIdx;
    uint16 loc_midElmntIdx;
    boolean OperationStatus = FALSE;
    uint16 prev_loc_midElmIdx = 0;
    uint16 is_midElmIdxSame_count = 0;
  
    if(LstElmntIdx >= FrstElmntIdx)
    {
        while (OperationStatus == FALSE)
        {
            loc_midElmntIdx = (startIdx + endIdx) / 2U ;
            if (ElmntToFind == InputArray[loc_midElmntIdx])
            {
                OperationStatus = TRUE;
                ReturnValue   = 0 ; 
            }
            else if (ElmntToFind > InputArray[loc_midElmntIdx])
            {
                /* if entire array was already checked*/
                if (startIdx == endIdx) 
                {  
                    OperationStatus = TRUE;
                    ReturnValue   = 1 ; 
                }
                else /* othewise, */
                {
                    startIdx = loc_midElmntIdx + 1U;
                }
            }
            else
            {
                /* if entire array was already checked*/
                if (startIdx == endIdx) 
                {  
                    OperationStatus = TRUE;
                    ReturnValue   = 1 ; 
                }
                else /* othewise, */
                {
                    endIdx = loc_midElmIdx - 1U ;
                }
            }
            if(prev_loc_midElmIdx != loc_midElmIdx)
            {
                prev_loc_midElmIdx = loc_midElmIdx;
            }
            else
            {
                is_midElmIdxSame_count++;
                /*as the divisor is 2 the same value can't return more that 2 times, hence if the same value is return more than
                * 2 times the loop should be braked
                */
                if(is_midElmIdxSame_count == 3)
                {
                    elmntNotFnd = 3;
                    /* Stop operation and return failure*/
                    OperationStatus = TRUE;
                    ReturnValue   = 1 ;
                }
            }
        }
    }
    else 
    {
        loopCntr = 0;
        /* Incorrect input arguments */
        ReturnValue = 1;
    }
    return ReturnValue;
}

`boolean` is not a standard C type. Include `` and use the standard `bool` type, together with `true` and `false`. — Some programmer dude, Jan 17 '23 at 07:16
As for the problem itself, have you tried to [*debug*](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) your program? For example by using a [*debugger*](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) to step through the code line by line while monitoring variables and their values? — Some programmer dude, Jan 17 '23 at 07:17
```int16_t``` is defined in ```stdint.h```, but where is ```uint16``` defined? — Harith, Jan 17 '23 at 07:22
They are all defined in the horrid land of C90 coding conventions. Because why program like it's the 21st century. — Lundin, Jan 17 '23 at 07:54
In any case, someone would have already debugged it for you if you would have provided a [mcve]. — Costantino Grana, Jan 17 '23 at 08:46
Hello All, after the debugging I found the mid element is return the same values from the 9th iteration and moreover the code I have posted here is only the function which needs some guidance from the forum members, thanks in advance!! — Prk651989, Jan 17 '23 at 08:48
I think your code is unnecessarily very complicated. It seems like you are writing C in another language. — Zakk, Jan 17 '23 at 08:49
Hi @Zakk my objective is to find the given number is preset in an array which size is more than 300 bytes, if it is present then it should returns success, if it is not present it returns failure, hence I tried binary search algorithm, if you can give your comments related to what you are pointing out as unnecessary codes which would be more helpful. — Prk651989, Jan 17 '23 at 08:59

score 1 · Answer 1 · answered Jan 17 '23 at 09:52

There's no such type called boolean in C. You have to #include <stdbool.h> to use the bool type. The same thing for uint16, you have to #include <stdint.h> and use uint16_t.

And your code is very complicated. You needlessly use a lot of variables to get one simple thing done.

Here is a more compact version:

bool binary_search(size_t start, size_t end, const uint16_t elem, const uint16_t array[])
{
    while (start < end) {
        size_t middle = (start + end) / 2;
        
        if (elem == array[middle])
            return true;
        if (elem < array[middle])
            end = middle;
        else
            start = middle + 1;
    }

    return false;
}

It returns true if the element is found, false otherwise.

Example:

int main(void)
{
    uint16_t array[] = {1U, 2U, 3U, 4U, 5U, 6U, 7U, 8U, 9U, 10U};
    const size_t size = sizeof array / sizeof array[0];
    const uint16_t elem = 10U;
    
    printf("%s\n", binary_search(0, size, elem, array) ? "Found" : "Not found");
}

Found

Few things to note:

size_t is the appropriate type for indexing arrays.
Use const (i.e. read-only) when you don't modify your variables.
Don't write C in Pascal style.

Binary search loop is not breaking when the search element input is not prsenting in the sorted array

1 Answers1