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 10 9658 fr*******@yahoo.com wrote: 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.
Vladimir S. Oka schrieb: fr*******@yahoo.com wrote:
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).
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

EMail: Mine is an /at/ gmx /dot/ de address. fr*******@yahoo.com wrote: Hi,
I have a single link list which is sorted.
<snip>
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> fr*******@yahoo.com wrote: 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 offtopic here. Try comp.programming.
Offtopic:
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 offbalance,
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.)

Ioan  Ciprian Tandau
tandau _at_ freeshell _dot_ org (hope it's not too late)
(... and that it still works...)
"Carl R. Davies" <nw*****@googlemail.com> wrote in message
news:11*********************@z34g2000cwc.googlegro ups.com... fr*******@yahoo.com wrote: Hi,
I have a single link list which is sorted. <snip>
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.
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.
</OT>
"Carl R. Davies" <nw*****@googlemail.com> wrote in message
news:11*********************@z34g2000cwc.googlegro ups.com... fr*******@yahoo.com wrote: Hi,
I have a single link list which is sorted. <snip>
How can I perform binary search on this link list. or should I perform search on right from the beginning.
<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.
</OT>
"stathis gotsis" <st***********@hotmail.com> writes: "Carl R. Davies" <nw*****@googlemail.com> wrote in message news:11*********************@z34g2000cwc.googlegro ups.com...
[...] 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.
There are sorting algorithms *much* worse than O(n^2), but as far as I
know only deliberately perverse ones. 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.
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).

Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
"Keith Thompson" <ks***@mib.org> wrote in message
news:ln************@nuthaus.mib.org... "stathis gotsis" <st***********@hotmail.com> writes: 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.
I was talking about the more common ones who deliberately opt for efficiency
and not the opposite. 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 the 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).
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.
"stathis gotsis" <st***********@hotmail.com> writes: "Keith Thompson" <ks***@mib.org> wrote in message news:ln************@nuthaus.mib.org...
[...] 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).
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.)

Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
"Keith Thompson" <ks***@mib.org> wrote in message
news:ln************@nuthaus.mib.org... "stathis gotsis" <st***********@hotmail.com> writes: 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.)
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). This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: danny van elsen 
last post by:
hello all,
I have an application in which I build a list<node>, with potentially
thousands of nodes.
each node has an "index", and all nodes are ordered by this index. this
index reflects a...

by: Ryan Graham 
last post by:
I totally bombed this question in an interview so I'm posting my answer here
for comments and suggestions... perhaps (god help me) I'm just not that
bright, but this works and seems to be fairly...

by: hn.ft.pris 
last post by:
I have the following code:
Tree.h defines a simple binary search tree node structure
########## FILE Tree.h ################
#ifndef TREE_H
#define TREE_H
//using namespace std;
template...

by: Rick 
last post by:
I have a large list of objects where each object has a unique
(nonoverlapping) date range. The list is sorted chronologically. What is
the most efficient way to search this list for a single...

by: zfareed 
last post by:
<code>
#include <iostream>
#include <fstream>
const int MAX_LENGTH = 10;
using namespace std;

by: assgar 
last post by:
Hi
I was using a schroll bar to display multiple rows of dynamically created from database records.
The scrolling was not displaying the data properly so I have decided to use pagination.
The...

by: Guy 
last post by:
Is there a better way to search identical elements in a sorted array
list than the following:
iIndex = Array.BinarySearch( m_Array, 0, m_Array.Count,
aSearchedObject );
aFoundObject= m_Array;...

by: Henrik Goldman 
last post by:
Hello,
I have a dataset which consist of a string username and string hostname as a
key and then an integer representing a count as the matching "second" value
in a pair.
So far I've used...

by: Atos 
last post by:
SINGLELINKED LIST
Let's start with the simplest kind of linked list : the singlelinked list which only has one link per node. That node except from the data it contains, which might be...

by: isladogs 
last post by:
The next Access Europe meeting will be on Wednesday 2 August 2023 starting at 18:00 UK time (6PM UTC+1) and finishing at about 19:15 (7.15PM)
The start time is equivalent to 19:00 (7PM) in Central...

by: erikbower65 
last post by:
Using CodiumAI's pragent is simple and powerful. Follow these steps:
1. Install CodiumAI CLI: Ensure Node.js is installed, then run 'npm install g codiumai' in the terminal.
2. Connect to...

by: kcodez 
last post by:
As a H5 game development enthusiast, I recently wrote a very interesting little game  Toy Claw ((http://claw.kjeek.com/))。Here I will summarize and share the development experience here, and hope it...

by: Taofi 
last post by:
I try to insert a new record but the error message says the number of query names and destination fields are not the same
This are my field names
ID, Budgeted, Actual, Status and Differences
...

by: DJRhino1175 
last post by:
When I run this code I get an error, its Runtime error# 424 Object required...This is my first attempt at doing something like this. I test the entire code and it worked until I added this 
If...

by: Rina0 
last post by:
I am looking for a Python code to find the longest common subsequence of two strings. I found this blog post that describes the length of longest common subsequence problem and provides a solution in...

by: lllomh 
last post by:
Define the method first
this.state = {
buttonBackgroundColor: 'green',
isBlinking: false, // A new status is added to identify whether the button is blinking or not
}
autoStart=()=>{

by: lllomh 
last post by:
How does React native implement an English player?

by: Mushico 
last post by:
How to calculate date of retirement from date of birth
  