Need help with writing this algorithm in code

Philip Harris

I have been mixed up on how to code this algorithm in c#...
It is the jump search algorithm 2.3.
Any hints or anything will be of help thank you.

4 Replies

Know the answer? Post it — somebody with the same question will find it here.

Vulpes11y ago
Accepted answer
Here's my attempt at coding that in C#.

The only awkward point is that Lists are zero based in C# whereas the algorithm seems to be assuming that they're 1-based. I've therefore reduced the index by 1 to allow for this:

using System;
using System.Collections.Generic;

class Program
{
static void Main()
{
var list = new List{3, 5, 7, 8, 10}; // already sorted
int lower = 1;
int upper = list.Count;
int jump = (int)Math.Sqrt(upper); // probably optimal value for jump
int[] search = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
foreach(int X in search)
{
int index = JumpSearch(list, lower, upper, jump, X);

if (index > 0)
{
Console.WriteLine("{0} was found at index {1}", X, index);
}
else
{
Console.WriteLine("{0} is not in the list", X);
}
}

Console.ReadKey();
}

static int JumpSearch(List list, int lower, int upper, int jump, int X)
{
if (lower < 1) throw new ArgumentException("lower must be greater than 0");
if (upper < lower) throw new ArgumentException("upper must not be less than lower");
if (jump < 1) throw new ArgumentException("jump must be greater than 0");
if (jump > (upper - lower + 1) ) throw new ArgumentException("jump must not be more than upper-lower+1");

int index = lower + jump - 1;

while(upper > index && X > list[index - 1]) // List is zero based
{
index += jump;
}

if (upper > index) upper = index;
return LinearSearch(list, index - jump + 1, upper, X);
}

static int LinearSearch(List list, int lower, int upper, int X)
{
for(int i = lower; i <= upper; i++)
{
if (list[i - 1] == X) return i; // List is zero based
}

return 0;
}
}

The output is:

1 is not in the list
2 is not in the list
3 was found at index 1
4 is not in the list
5 was found at index 2
6 is not in the list
7 was found at index 3
8 was found at index 4
9 is not in the list
10 was found at index 5
Philip Harris11y ago
Makes sense I guess I should have looked it as pseudo code and not only thought in c#, Thanks for clearing that up should go smoother for me hopefully finishing up this semester.

Many thanks Vulpes.... YOU ROCK!
Vulpes11y ago
Well, what we can see just tells us how to implement the algorithm using pseudo-code. It doesn't tell us how 'jump search' actually works.

So, I've simply translated the pseudo-code into C# code. As previously mentioned, the only awkward point is that List in C# is zero based, not 1-based, so I've adjusted for that.

No definition was given for the LINEAR.SEARCH method so I simply assumed that we're supposed to iterate through the list, returning the 1-based index if X is found or 0 otherwise.

The part between the {..} is simply a comment but I used the information in that to check the arguments are acceptable and consistent with each other.

Thinking about it some more, perhaps we ought to add another line to make sure 'upper' isn't more than the number of elements in the list:

if (upper > list.Count) throw new ArgumentException("upper can't be more than the number of elements in the list");
Philip Harris11y ago
Thank you I keep getting caught up in the wording of the text I believe do you have any tips on making it easier to interpret?