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;
}

Answer 1

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.