Trouble Understanding C++ Sequential Search

Question

I am new to C++ and am having difficulty understanding this function. Could someone walk me through it?

int seqSearch(int [ ] list, int target)
{
    //precondition:  The list is in non-decreasing order
    //postcondition:  The method returns -1 if the target is not in the list.  If the target
    //is in the list, the method returns the index of the first occurrence of the target.
    int result = -1;
    boolean foundBigger = false;
    int i = 0;
    while (result == -1 && !foundBigger && i < list.length)
    {
        if (target == list[i])
            result = i;
        else if (list[i] > target)
            foundBigger = true;
        //endif
        i++;
    }  //endwhile
    return result;
}

Answer 1

If this is working code then its DEFINETELY not c++. The boolean operations in the while loop would have to be enclosed in separate parenthesis for order of operations and c++ doesn't have a .length property for arrays (java allows for both of these which makes me thing it's written in java).The logic behind it still remains the same though.

You first initialize your result int(the one that's to be returned) and a boolean that checks if you've passed the element that you want. As long as you haven't found what your looking for and you haven't 'passed' the target item you keep going.

If you've found your target then your result int is changed to the correct index and the next time the loop checks its conditions the index will be over -1 and represent a real number so the method will end and return an index.

The second statement checks to see if you've passed the int that you're looking for. You know the list is sequential so if the value you're currently on is higher than the value you're looking for and you didn't find the item then you change the foundBigger boolean which will end the loop next time the conditions are checked.

If none of these conditions are met then you will eventually go past the end of the list searching so once you've reached the end of your list you know the item wasn't in the list so you still return -1.

Answer 2

// precondition:  The list is in non-decreasing order
// postcondition:  The method returns -1 if the target is not in the list.  If the target
// is in the list, the method returns the index of the first occurrence of the target.
int seqSearch(int [ ] list, int target)
{
    int result = -1;                                    // Set result to 'not-found' value
    // Also we want to stop search if smth bigger than `target' will be found
    // Remember the original list is assumed to be sorted, so first value
    // bigger than `target' means: no need to continue, it is guarantied that `target'
    // is nto here!
    boolean foundBigger = false;
    int i = 0;                                          // Initial index to start search
    // Repeat 'till `target' not found AND not found smth bigger that requested target
    // and current index less than the list size...
    while (result == -1 && !foundBigger && i < list.length)
    {
        if (target == list[i])                          // Is current item equal to the requested?
            result = i;                                 // Remember result index (this will break the loop)
        else if (list[i] > target)                      // Is current item bigger than the requsted?
            foundBigger = true;                         // Yep, will break the loop w/ no result to return
        //endif
        i++;                                            // move to next item in the list
    }  //endwhile
    return result;                                      // Return the result,  whatever it is
}

Answer 3

when result is == -1 and foundBigger is true and then the size of the array that you pass to the function is more than 0

then it goes inside the while loop

if even of the one of the above criteria is not full filled then it would not go inside the loop it would just return the value of the return

then if the value that you pass to the function using target parameter equals to i value of array list then you assign result to he value of i

if the target value is less than to i value of array list then the foundBigger is assigned true so again when you come into the while loop you cannot fulfill the above criteria

if none of the above works then i is incremented by 1 and it comes out of the while loop

it goes until you find the in which position the target value is saved if target value is not in the array then it would return result -1

or else it would return the location

Answer 4

It is trying to find if a target number is present in the list, where the number in list are stored in descending order.

The loop continues,

1. Till the target is not found. (Condition:result == -1) ( If target found then result != -1 and the loop breaks, returning the index of the element.

2. or Till the element in the list is bigger than the target. ( Condition:!foundBigger ) ( As the list is in descending order, if it finds a number which is less than the target, so their would be no chance of finding the number in the remaining list. So this means it is not present in the list and the loop should break.)

3. or Till the whole list is rendered and its not found. (Condition: i < list.length)

Hope its clear now.

Answer 5

Hmm, "non-decreasing order". A better word for it is ascending order :-)

The function assumes the list is in ascending order. Starting with the first item in the list (list[0]) , compare with the item you are looking for (ie, "target"). If equal, set result to index "i". If not, increment i and continue loop. Go through each item one by one until:

(a) you find "target", OR

(b) the current item is bigger than your "target" (quit at this point since no point goind on since your list is ordered)

Return value is the index in the list where you found "target" or -1 if not found.