Sequential searching with sorted linked lists

Question

struct Record_node* Sequential_search(struct Record_node *List, int target) { 
    struct Record_node *cur;
    cur = List->head ;
    if(cur == NULL || cur->key >= target) {
        return NULL;
    }
    while(cur->next != NULL) {
        if(cur->next->key >= target) {
            return cur;
        }
        cur = cur->next;
    }
    return cur;
}

I cannot interpret this pseudocode. Can anybody explain to me how this program works and flows? Given this pseudocode that searches for a value in a linked list and a list that is in an ascending order, what would this program return?

a. The largest value in the list that is smaller than target
b. The largest value in the list that is smaller than or same as target
c. The smallest value in the list that is larger than or same as target
d. Target
e. The smallest value in the list that is larger than target

And say that List is [1, 2, 4, 5, 9, 20, 20, 24, 44, 69, 70, 71, 74, 77, 92] and target 15, how many comparisons are occurred? (here, comparison means comparing the value of target)

EDIT: @Stephen I am sorry if I have been rude asking my question.

Well, since I am used to programming in Visual Basic, I understand 'cur->key' in line 4 of the program as 'cur is larger than or same as key', but since '+=' means 'former value plus the latter value equals the latter value', I can interpret '->' in the same manner as '+=' This part is one of the problems I am facing.

The second problem I am facing is the use of pointers in Record_node(if it is a pointer). I'm not even sure if I know what I don't know! I understand this program as some kind of a recursive algorithm.

Answer 1

Well, since I am used to programming in Visual Basic, I understand 'cur->key' in line 4 of the program as 'cur is larger than or same as key', but since '+=' means 'former value plus the latter value equals the latter value', I can interpret '->' in the same manner as '+=' This part is one of the problems I am facing.

That's where the problem is, I'm glad you clarified that :)

This code is written in c (or c++). That language uses -> to dereference pointers and point to members of a struct. IIRC, VB doesn't have pointers, so you would say struct.member or cur.next.

while (cur->next != NULL) {   // While current's next node isn't NULL.
}

NULL is being used to signify the end of the list.

Evaluating the cur->next->key means "the key of the node after the current one". It may help you visualize this if you draw a linked list with ascending values and trace the program.

At some point during execution of the while loop, you'll have this:

+-+  +-+  +-+
|2|--|4|--|7|--NULL
+-+  +-+  +-+
 ^    ^    ^
 |    |    |
 head cur  cur->next

BTW, the real greater-than-or-equal-to operator is >=.

BTW2, it's not recursive. Recursive would be a function that calls itself (you could implement this recursively). This function is iterative (it uses loops). An example of a recursive algorithm is:

node* Sequential_search(List *list, int target) {
  if (!list) return NULL;
  if (target == list->key) return list;
  return Sequential_search(list->next, target);
}

Hope that helps!

Answer 2

You might find it helpful to review a list of C operators and their precedence, especially coming from VB. I applaud your bravery for jumping into a link list first .. but you might want to spend some time getting the basics of pointers down before you start on a list implementation.

This is supplemental to Stephen's great answer, which I've up-voted.