11
How can I perform a binary search on a simple chained list with head? Also if it is possible to do this, if there is some special method. In the EP I can not count beforehand the amount of elements of this list, I have to do the search and insert a cell between q->prox and p.
11
It is possible to apply the Binary Search to a chained list, however, you will lose the main reason to use the Binary Search, the factor it has complexity O(log n).
The fact is that binary searches applied in arrays are efficient, because the elements of an array are allocated in memory in a contiguous manner, which makes access to any element a trivial operation, O(1).
On the other hand, in a chained list there is no guarantee that the elements will be allocated in a contiguous manner and, even if they were, there is no way to access them in time O(1). That way, to find the middle of the list, you need to unravel an algorithm that will have to visit us until you find the middle. This operation already slows down the algorithm. The worst case of a binary search in a chained list is O(n log n).
Because of this, sequential searches on chained lists tend to be faster, since O(n) < O(n log n). See update below for cases where it might be worth using binary search in a chained list.
About the algorithm, this one looks interesting: http://www.algo-faq.com/Linked-List/Find-the-middle-node-of-a-linked-list.php
The challenge, compared to arrays, is to determine the middle of the list. For this, the above algorithm uses a different approach that does not require knowing the size of the list previously.
This same algorithm is described in this article: http://www.ijcsit.com/docs/Volume%205/vol5issue02/ijcsit20140502215.pdf
Since this is an exercise, I would go the way mentioned above.
There are cases where it can make sense to use binary search in a chained list, I explain.
Suppose the task of making the comparison is costly. In this case, the binary search algorithm may make sense, as O(log n) comparisons are made. In part O(n) no comparison is made, but only the list is searched to find the medium.
On the other hand, if the algorithm is sequential search then, for each item, the comparison is performed. What can become something more costly compared to the binary search scenario.
3
Whereas you can get the amount of elements, you can figure out which is half of the list. With this you would have to go from the head of the list to the middle and compare the desired value with the middle node, if it is larger you should consider the middle position the beginning of the list and find the middle of the new beginning until the end, or if it is smaller. The problem is that you have not gained any performance.
Below a code I have not tested, but I believe it should be close to what you need.
celula *buscaR (int qnt, int x, celula *ini)
{
if (ini->prox == NULL)
return NULL;
p = ini->prox;
int count = 0;
while (p != NULL && p->conteudo != x) {
p = p->prox;
if(count++ == qnt/2){
if (p->prox->conteudo == x)
return p->prox;
else{
if(p->prox->conteudo > x){
return buscaR (qnt/2, x, p->prox);
}else{
return buscaR (qnt/2, x, ini->prox);
}
}
}
}
}
Updating
If we consider the excerpt "No EP can not count beforehand the amount of elements of this list" the answer is:
It will not be possible to apply a solution since it is essential in the search binary terms quantity of list elements.
In the statement of the problem does not say yes or no, if we could count the elements, there is no apparent restriction, which asked the teacher he implied that we should research on this question, whether it was possible or not.
A linked list does not benefit from binary search - in your code you do a linear search for the list looking for the element - (and there is another error: you do not return the position when you find the element - the case where p->conteudo == x no while)
I informed at the end of the text that there is no performance gain. The reason to apply a binary scan to an ordered chained list is because it is an exercise, it makes no sense and gain by considering sequential search to find the middle of the list.
Eventually there may be a gain. See my reply update.
"In EP I can not count beforehand the amount of elements of this list"
The function statement is: cellula *Buscabinaria (cellula *p, cellula *list); this function returns me a pointer to then insert another function, in the list... I’m trying to implement using the two pointers solution, as in the article presenting, using a fast pointer and a slow one, using an internal while loop, apparently going to work, what’s catching are the stopping conditions.
In the algorithm option I have presented, it is not necessary to count beforehand the amount of elements in the list. On the contrary, the list may have arbitrary size that the algorithm will work. The only premise, of course, is that the list is sorted before the execution of the algorithm.
Browser other questions tagged c quest chain-list
You are not signed in. Login or sign up in order to post.
The list is ordered, I import it from a text file, but the amount of elements "I do not know beforehand".
– Marcelo de Sousa
And you can count the elements ?
– Mayllon Baumer
I did not understand why this question was classified as too wide.
– cantoni
What do they mean "EP",
pandq->prox, within the problem?– Gabe
@Marcelodesousa, I think it’s worth it you give an improved in your question. You’ve already had 10 votes with her like this. If you do this, your question has a chance to be reopened and gain more community attention, with more answers and discussion on this interesting topic.
– cantoni