Hey guys need help from you. I've seen people get help here. I am a web developer/graphic designer but I have to take this class its a requirement and i am not much of a programmer. If you give me a good pseudo code it will be fine. I understand the concept but i cannot write from the scratch. If you are going to use language then you can use C. I hope i get some help. And please dont flame this thread. Thanks.

When the collection of data is large, a large number of comparisons may

still be needed to do a binary search. For example, a telephone directory of a large city

could easily take about 25 comparisons per search. To improve this, multiway searching

uses a general tree, which is a tree data structure that can have more than two children.

In multiway searching, we store a few keys in each tree node, and the children represent

the subtrees containing (a) the entries smaller than all the keys, (b) the entries larger

than the first key but smaller than the rest (c) the entries larger than the first two keys

but smaller than the rest, and so on. The figure below shows an example of a general

tree that can be used for multiway searching. In the root of this tree we have the keys of

6 and 10, so if we are looking for a key less than 6, we would take the left branch. If we

are looking for a key between 6 and 10, we would take the middle branch, and for a key

larger than 10, we would take the right branch.

Write an algorithm to do a multiway search. For your answer you can assume that

each node has two arrays called Keys[3] and Links[4] and that you have a function

called Compare(keyList, searchKey) that returns a positive integer indicating the key that

matches or a negative integer indicating the link to take. (For example, Compare([2,6,10],

6) would return a value of 2 because the second key matches, and Compare([2,6,10], 7)

would return a value of −3 because 7 would be found on the third link associated with the

gap between the second and third key values.) When you have finished your algorithm,

do a wort-case and an average-case analysis, assuming that the tree is complete and each

internal node has four children. (You might want to draw a sample tree.) What would

be the impact on your two analyses if the tree was not complete or if some internal nodes

had fewer than four children?

bump

Not sure if this is correct


Multiwaysearch(keyList,start,end,searchKey)

//keylist        the list of keys
//start           the index of the first value to consider
//end            the index of the last value to consider
//searchKey the element of list we want

if start<end then
   result= compare(keyList,searchKey)
   if result > 0 then
      return result
   else
   
     if result < 0 then
        return Multiwaysearch(keyList, links[abs(result)],end,searchKey)
    end if
end if
      

Thank you so much tech guy, you are great.

I will keep this thread alive to see more answers.

Thanks TechGuy and thanks Sajha community.

you know what
if result < 0 then
        return Multiwaysearch(keyList, links[abs(result)],end,searchKey)
    end if
end if


should be

Multiwaysearch(keyList,searchKey)
.
.
.
.


if result < 0 then
        return Multiwaysearch( links[abs(result)],searchKey)
    end if
end if

no need for start and end 
but this will cause and infinite recursion if NO MATCH...

lets see if someone has taken Algorithm Analysis class.

Not sure if you are looking for binary search. Looks like it is binary search though
Here is the function for binary search

int Multiwaysearch(keyList,start,end,searchKey)
{
    int k = 0;
   while( start <= end)
       {
               k = ( start + end)/2;
              if (searchKey = = keyList[k])
                  return k; // returns this position if  searchKey is found in keyList
              if (searchKey < keyList[k])
                   end = k -1;
              else
                  start = k+1;
        }
      return -1; // returns -1 indicating that no match was found
      return ( -k) // this might return the position the number would be found if the number is not in the  keyList.
}

 You don't have to use compare function here, but if you need to you could now modify anyway.
Hope this helps