Binary search in linked list [closed]

It is possible to apply Binary Search in a linked list, however, you will lose the main reason for using Binary Search, the factor of having 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 contiguously, which makes access to any element a trivial operation, O (1).

On the other hand, in a linked list there is no guarantee that the elements will be allocated contiguously, and even if they were, there is no way to access them in O (1) time. Thus, to find the middle of the list, it is necessary to unlock an algorithm that will have to visit us until we find the medium. This operation already makes the algorithm slower. The worst case of a binary search in a linked list is O (n log n).

Because of this, sequential searches on linked lists tend to be faster, since O (n) < O (n log n). See update below for cases where it might be worthwhile to use binary search in a linked list.

About the algorithm, this looks interesting: link

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: link

Since this is an exercise, I would go by the path quoted above.

Update

There are cases where it might make sense to use binary search in a linked list, explain.

Suppose that the task of making the comparison is costly. In this case, the binary search algorithm may make sense, because O (log n) comparisons are made. In the part O (n) is not made comparison, but only goes through the list to find the means.

On the other hand, if the algorithm is sequential search then for each item the comparison is performed. This can become more costly compared to the binary search scenario.

Considering that you can get the amount of elements, you can figure out which is half the list. With this you would have to go from the top 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 to the end, or the otherwise. The problem is that you have no performance gain.

Below a code I have not tested, but I think 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);
                }
            }
        }
   }
}

Update

If we consider the phrase "In EP I can not count the number of elements of this list beforehand" the answer is:

  

It will not be possible to apply a solution since it is primordial in the search   binary terms quantity of list elements.