0

I am having trouble understanding why the bool search function is working the way it does.

I had gone through the Section for Week 3. While I understand the logic of binary search, I don't understand how the computer is exactly "searching." Sure, we delineated bounds in different cases relative to the middle value, but those boundaries aren't even passed into the function.

How does the computer know to look within the bounds of a list if there isn't some algorithm that tells the computer to look at the elements, one at a time?

Since that is how a computer "searches." Although I understand that binary search narrows down the elements in the list being examined, I thought that the searching would still involve multiple linear searches with smaller n. All in all, there is no explicit mention of a searching algorithm within the function declaration itself.

5

There are two basic ways for implementing a binary search algorithm.

  1. using recursion.
  2. using loops.

Given values, a global int array that we're searching for value in. min, the minimum index, and max, the maximum index in the array/sub-array,

The Pseudocode for the Recursion Way Might Be

bool search (int min, int max, int value)
{
    // the base case
    if (min > max)
    {
        return false // value wasn't found
    }

    calculate the middle index and store it in mid

    if (value < values[mid])
    {
        set max to mid - 1 // update max
    }
    else if (value > values[mid])
    {
        set min to mid + 1 // update min
    }
    else
    {
        return true // value was found
    }

    return search(min, max, value) // the recursive call (NOTICE that we're passing the new boundaries -- min and max)
}

The Pseudocode for the Loop Way Might Be

bool search (int n, int value) // n is the length of the array
{
    create and set min to 0
    create and set max to n - 1

    while (min <= max)
    {
        calculate the middle index and store it in mid

        if (value < values[mid])
        {
            set max to mid - 1 // update max
        }
        else if (value > values[mid])
        {
            set min to mid + 1 // update min
        }
        else
        {
            return true // value was found
        }
    }

    return false // value was not found
}

So in both cases, we're updating either min or max as we need to and recalculating mid which in turn updates it and that's how our program knows the new boundaries.

2
  • Thanks Kareem, although just one question, I thought we cannot change the parameters of the bool search(int value, int values[], int n) function. But is it okay to not use the int values[], like you show above in the loop method? We won't get an error that we did not use the parameter? Thanks.
    – Azurespot
    Aug 24 '14 at 2:27
  • @NoniA. I actually assumed that the array named values is declared as a global variable. And no, you're not supposed to change the declaration of search(). In your case, you should probably used the array passed to this function instead. In general, we declare functions to receive arguments because we want to use them. There's no point of having a parameter that we're not gonna use. However, nothing will yell at you if you didn't use any of the parameters.
    – kzidane
    Aug 24 '14 at 21:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .