Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

xe_sphinx

Binary Search

This topic is 6168 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi Everyone How can I implement A Binary search into a LinkedList. I have done a Binary Search with an array, but I did not manage to do it with a LinkedList. Does anybody know how to do that, or direct me to a place in the net where it is explained. Thanks Windows (N): A 32 Bit patch to a 16 bit graphical interface based on a 8 bit operating system originaly encoded for a 4 bit processor written by a 2 bit company that can''''t stand 1 bit of competition.

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
Because the nodes of a linked list can reside at any location in memory (as opposed to an array, which uses a contiguous portion), a traditional binary search will fail. Look into skip lists in order to efficiently search a linked list.

Share this post


Link to post
Share on other sites
*throws stuff together*

  struct binNode_s {
dataType data;
struct binNode_s *parent;
struct binNode_s *left;
struct binNode_s *right;
} binNode_t;


hope it helps ;X

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
That''s a binary search tree, not a traditional linked list. Don''t confuse the poor guy!

Share this post


Link to post
Share on other sites
It is possible. Create a sorted array of pointers to your linked list nodes, then perform your binary search on the array.

Share this post


Link to post
Share on other sites
quote:

Create a sorted array of pointers to your linked list nodes


Considering the sort takes an order of magnitude more time than a linear search does, that''s not much of a solution :p but does answer the question.

struct btreeNode
{
btreeNode node[20];
btreeNode* branches[20];
int iUsed;
};

...
You were joking, right xe_sphinx?

Magmai Kai Holmlor
- Not For Rent

Share this post


Link to post
Share on other sites
What I actually mean is. I have a sorted Linkedlist (is sorted all the time) and I want to search for a specific item.
I could use linear search, but i need performance.

This is the binary search for an array:
=======================================
void BinarySearch(int left, int right, int test)
{
while (flag == 0 && left <= right)
{
middle = (left+right) / 2;
if (test == listmain[middle])
{
cout << "match found " << listmain[middle];
flag = 1;
}
else
{
if (test > listmain[middle])
{
left = middle + 1;
}
else
{
right = middle - 1;
}
BinarySearch (left, right, test);
}
}



I have tried to implement it into my LinkedList:
================================================
char * EnemyLinkedList::BinarySearch(int iLow, int iHigh, char * szName)
{
Enemy * pTemp = pHead;
UINT middle;

while (SearchFlag == false && iLow <= iHigh)
{
middle = (iLow+iHigh) / 2;

for (UINT i = 0; i < middle; i++)
pTemp = pTemp->pRight;

if (szName == pTemp->GetName())
{
//cout << "match found " << pTemp->GetName());
SearchFlag = true;
return (pTemp->GetName());
}
else
{
if (szName > pTemp->GetName())
iLow = middle + 1;
else
iHigh = middle - 1;

BinarySearch (iLow, iHigh, szName);
}
}
===================================

But this one does not work, any ideas why?


Windows (N): A 32 Bit patch to a 16 bit graphical interface based on a 8 bit operating system originaly encoded for a 4 bit processor written by a 2 bit company that can''''t stand 1 bit of competition.

Share this post


Link to post
Share on other sites
In general, linked lists are not a good choice of data structure for ANYTHING. That is primarily because of their inherent inefficiency.

If you want fast insert, remove, search, and ordered traversal, which is what it sounds like you want, use some form of balanced binary search tree.

Share this post


Link to post
Share on other sites
quote:
Original post by c_wraith
In general, linked lists are not a good choice of data structure for ANYTHING. That is primarily because of their inherent inefficiency.


Right, that''s why they''re in every data structures book ever written; they just like screwing with our minds. Put down the drugs, c_wraith.

Every kind of data structure has different uses and different attributes. If any two had the same, they''d be the same data structure. There is no magic bullet data structure that is better than all others. There might be data structures that are worse than all others, but they wouldn''t make publication. Linked lists are not useless.

Linked lists rule at splicing. There''s no other data structure that can merge two containers together in constant time as simply as linked lists. They''re extremely useful in many situations.

However, linked lists have just about the worst random access of any data structure, which is what you need if you want to do a search through sorted data. In fact, "sorted" and "linked list" are two phrases that should never appear together in the same sentence. To get proper performance, and since you''re sorting your data (indicating that the sequence of insertion is not important), you really need to switch to a tree or hash table.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!