single link list , binary search

[free2cric]

Hi,

I have a single link list which is sorted.

structure of which is like

typedef struct mylist
{
int num;
struct mylist *next;
} MYLIST;

How can I perform binary search on this link list. or should I perform
search on right from the beginning.

Thanks,
Cric

 

[Vladimir S. Oka]

Hi,

I have a single link list which is sorted.

structure of which is like

typedef struct mylist
{
int num;
struct mylist *next;
} MYLIST;

How can I perform binary search on this link list. or should I perform
search on right from the beginning.

Not really a C question (probably better asked in comp.programming),
but:

<OT>
Efficient binary search requires that you can quickly access any element
(usually by its index), so it's more naturally suited to arrays. If,
however, you're forced to use linked list (and you say it's sorted),
yuo have two ways of approaching this. One is to copy the whole list
into an array and then perform binary search there (not memory
efficient). The other would be to keep everything in the linked list,
and traverse it from the beginning to the required element whenever you
need to test one. In terms of speed, I'd expect the first to be
quicker, as you traverse the whole list only once, although copies may
foul this up. The speed of the second approach depends on the list
contents and exactly which element you're after.
</OT>

--
BR, Vladimir

Sometimes I live in the country,
And sometimes I live in town.
And sometimes I have a great notion,
To jump in the river and drown.

 

[Michael Mair]

Not really a C question (probably better asked in comp.programming),
but:

<OT>
Efficient binary search requires that you can quickly access any element
(usually by its index), so it's more naturally suited to arrays. If,
however, you're forced to use linked list (and you say it's sorted),
yuo have two ways of approaching this. One is to copy the whole list
into an array and then perform binary search there (not memory
efficient).

Note: If the linked list elements are not negligible in size, then
rather keep an array of pointers to the list elements.

The other would be to keep everything in the linked list,
and traverse it from the beginning to the required element whenever you
need to test one. In terms of speed, I'd expect the first to be
quicker, as you traverse the whole list only once, although copies may
foul this up. The speed of the second approach depends on the list
contents and exactly which element you're after.
</OT>

Cheers
Michael

 

[Carl R. Davies]

Hi,

I have a single link list which is sorted.

How can I perform binary search on this link list. or should I perform
search on right from the beginning.

<OT>
I think keeping a single linked list sorted must be a big overhead. Are
you:

1. Start from first element.
2. Look at next elements value.
3. If insert value is less than next element value, then insert here,
exit.
4. Else move to next node, goto 2.

If yes, then I believe this is O(n). i.e. you're potentially looking at
every element in the list if your insert value is greater than any
value in the list. This is slow.

Searching will also be O(n), you have to look at potentially every
element in the list. I guess you can exit when you know you're past
your value.

If inserting and searching is done often maybe you should consider a
binary tree? You get sorting for free and searching is O(log N).

Hope this helps.
</OT>

 

[Nelu]

Hi,

I have a single link list which is sorted.

structure of which is like

typedef struct mylist
{
int num;
struct mylist *next;
} MYLIST;

How can I perform binary search on this link list. or should I perform
search on right from the beginning.

This question is off-topic here. Try comp.programming.
Off-topic:
The answer is: you can't. You could simulate it by creating a function
to parse the list to a given element and return the element but this is
not a direct access to your elements and the complexity of the
algorithm changes (well, it's a different algorithm altogether). You
could use binary trees and keep the elements sorted. The problem with
binary trees is that if you choose to implement a simple binary tree
you will often run into situations where they are way off-balance,
meaning that searching an element into a tree may require you to parse
every element of the tree much like you would do with your list. If you
decide to use trees then read about AVL trees and red and black trees.

(If you create nodes in a sorted binary tree in this order: 1, 2, 3, 4,
5, 6 using the natural ordering of integers, then you will end up with
something similar to a single linked list.)

 

[stathis gotsis]

<OT>
I think keeping a single linked list sorted must be a big overhead. Are
you:

1. Start from first element.
2. Look at next elements value.
3. If insert value is less than next element value, then insert here,
exit.
4. Else move to next node, goto 2.

If yes, then I believe this is O(n). i.e. you're potentially looking at
every element in the list if your insert value is greater than any
value in the list. This is slow.

This is insertion sort, and it is O(n^2) when sorting n elements and yes it
is the worst you can get.

Searching will also be O(n), you have to look at potentially every
element in the list. I guess you can exit when you know you're past
your value.

O(logn) and no you do not have to look at every element in the list even in
he worst case.

 

[stathis gotsis]

<OT>
If inserting and searching is done often maybe you should consider a
binary tree? You get sorting for free and searching is O(log N).

You could get O(n) in the worst case of a degenerate tree that looks like a
list. Trees must be kept weighted.

 

[Keith Thompson]

This is insertion sort, and it is O(n^2) when sorting n elements and yes it
is the worst you can get.

There are sorting algorithms *much* worse than O(n^2), but as far as I
know only deliberately perverse ones.

O(logn) and no you do not have to look at every element in the list even in
he worst case.

Searching a linked list is O(n); you can't get to any node without
first traversing all the previous nodes. (The number of nodes you
visit will be n/2 on average; that's still O(n), of course.) A binary
search on a sorted array is O(log n).

 

[stathis gotsis]

There are sorting algorithms *much* worse than O(n^2), but as far as I
know only deliberately perverse ones.

I was talking about the more common ones who deliberately opt for efficiency
and not the opposite.

Searching a linked list is O(n); you can't get to any node without
first traversing all the previous nodes. (The number of nodes you
visit will be n/2 on average; that's still O(n), of course.) A binary
search on a sorted array is O(log n).

You mean that searching a linked list using the linear search is O(n). The
binary search will perform O(log n) comparisons, but we will have the
traversal overhead added to that. For the binary search to be effective one
can create an array of pointers to the list's nodes, which is equivalent to
the sorted array you mentioned.

 

[Keith Thompson]

You mean that searching a linked list using the linear search is O(n).

Of course.

The binary search will perform O(log n) comparisons, but we will
have the traversal overhead added to that. For the binary search to
be effective one can create an array of pointers to the list's
nodes, which is equivalent to the sorted array you mentioned.

You can't do a binary search on a linked list. If you create an array
of pointers, you can do a binary search on the array of pointers. (I
suppose you *could* call that a binary search on the linked list, but
IMHO that would be misleading.)

 

[stathis gotsis]

Of course.


You can't do a binary search on a linked list. If you create an array
of pointers, you can do a binary search on the array of pointers. (I
suppose you *could* call that a binary search on the linked list, but
IMHO that would be misleading.)

Yes, it is rather meaningless to do a binary search on a linked list, that
is why i supposed that the OP would create some other data structure for the
sake of performing a BS which would then be O(log n).