Sequential searching with sorted linked lists
Posted
by John Graveston
on Stack Overflow
See other posts from Stack Overflow
or by John Graveston
Published on 2010-05-16T13:57:41Z
Indexed on
2010/05/16
14:00 UTC
Read the original article
Hit count: 188
c
|linked-list
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)
© Stack Overflow or respective owner