I want to write some methods like insert(), delete() and find() in an ordered array using binary search
ordered array
Collapse
X
-
Originally posted by morris11I want to write some methods like insert(), delete() and find() in an ordered array using binary search
You can do experiments from this link if you like...
And then, post your question with your best effort attached... ( code )...
sukatoa...Comment
-
This is what i've done so far for find() method:
[CODE=java]public int find(double searchKey)
{
int lowerBound = 0;
int upperBound = nElems-1;
int curIn;
while(true)
{
curIn = (lowerBound + upperBound ) / 2;
if(a[curIn]==searchKey)
return curIn;
else if(lowerBound > upperBound)
return nElems;
else
{
if(a[curIn] < searchKey)
lowerBound = curIn + 1;
else
upperBound = curIn - 1;
} // end else divide range
} // end while
}[/CODE]Comment
-
Your function works well. So what;' the problem? Enhancement? ok.
a) check for lowerBound > upperBound should be done right after modifying these 2 variables, so it will not go inside an unneeded extra step of the loop.
b) there is no need to put an"else"-clause if you return a value inside the "if"-clause. That makes the souce code smaller and you can understand better.
c)You should returning the position of the string before which you need to insert the new string (and not always the array size). Then you can use this function also for "insert()". That means return "lowerBound ". Shift all strings one index position up, starting from returned position, and insert new string at free place.
If you don't want to allow multiple strings with the same name in your array, just compare for equality at currently given position and if true, don't insert.
Assume: nElemens = 3
Trace: example: String is greater than all others:
Init: lowerBound = 0, upperBond=2,
1. step: curIn = 1. searchKey is greater --> lowerBound = 2
2. step: curIn = 2. searchKey is greater --> lowerBound = 3
3. step: curIn = 2 lowerBound > upperBound --> return 3
ok.
Trace: example: String is smaller than all others:
1. step: curIn = 1. searchKey is smaller --> upperBound = 0
2. step: curIn = 0. searchKey is smaller--> upperBound = -1
3. step: curIn = 0 lowerBound > upperBound --> return 3
??? should return 0
Trace: example: String is greater than first one (index=0) ,but smaller than second (index=1):
1. step: curIn = 1. searchKey is smaller --> upperBound = 0
2. step: curIn = 0. searchKey is greater--> lowerBound = 1
3. step: curIn = 0 lowerBound > upperBound --> return 3
??? should return 1
Trace: example: String is greater than second one (index=1) ,but smaller than last one (index=2):
1. step: curIn = 1. searchKey is greater --> lowerBound = 2
2. step: curIn = 2. searchKey is smaller--> upperBound = 1
3. step: curIn = 0 lowerBound > upperBound --> return 3
??? should return 2Comment
-
this is what i've done for insert() and delete() methods using linear search:
public void insert(long value)
{
int j;
for(j=0; j<nElems; j++)
if (a[j]>value)
break;
for(int k=nElems; k>j; k--)
a[k]= a[k-1];
a[j] = value;
nElems++;
}
public boolean delete(long value)
{
int j = find(value);
if (j==nElems)
return false;
else
{
for(int k=j; k<nElems; k++)
a[k]= a[k+1];
nElems--;
return true;
}
}
How can i transform these 2 methods to binary search?Comment
-
Originally posted by morris11this is what i've done for insert() and delete() methods using linear search:
public void insert(long value)
{
int j;
for(j=0; j<nElems; j++)
if (a[j]>value)
break;
for(int k=nElems; k>j; k--)
a[k]= a[k-1];
a[j] = value;
nElems++;
}
public boolean delete(long value)
{
int j = find(value);
if (j==nElems)
return false;
else
{
for(int k=j; k<nElems; k++)
a[k]= a[k+1];
nElems--;
return true;
}
}
How can i transform these 2 methods to binary search?
You are already using it in your "delete" method, so why don't you use it also for your "insert" method?
As I told you already in the previous post, you must return variable "lowerBound " in your previous binary search algorithm to know the insert position of the new record. Then you must do the same that you have done in the code above: shift all elements starting from this position one up. At the end you can insert the new record at this position.
One question: do you understand the code you have given here? I mean did you develop it yourself or did you just copy it from somewhere without understanding?
If you just copied, then make a Trace (as what I did in last posting) to get an understanding first. Or try to develop the code yourself to get an understanding. Else all my suggestions are for nothing if they cannot be understood. I hope I am mistaken, but I have no other explanation for the fact that I gave you the solution in the posting before and you ask for it again.
If you cannot understand something I wrote, please don't hesitate to ask exactly what sentence you did not understand, and I will be happy to give you further explanation.Comment
-
Honestly, I didn't develop the code myself , but i understood the find() method how it works, i mean the one i gave and not your suggestion. My problem is that I am not good in java; means i couldn't translate your ideas into code even I understood them ; so please, if it is possible, translate this part of your suggestion into code:
"you must return variable "lowerBound " in your previous binary search algorithm to know the insert position of the new record. Then you must do the same that you have done in the code above: shift all elements starting from this position one up. At the end you can insert the new record at this position."Comment
-
Originally posted by morris11Honestly, I didn't develop the code myself , but i understood the find() method how it works, i mean the one i gave and not your suggestion. My problem is that I am not good in java; means i couldn't translate your ideas into code even I understood them ; so please, if it is possible, translate this part of your suggestion into code:
"you must return variable "lowerBound " in your previous binary search algorithm to know the insert position of the new record. Then you must do the same that you have done in the code above: shift all elements starting from this position one up. At the end you can insert the new record at this position."
This forum is here to help you. It is not here to deliver spoon-feed code or do your assignment for you fully for free.Comment
-
Originally posted by chaarmannActually, if I write <<you must return variable "lowerBound ">> and you don't know from this instruction that you must replace line 13 in your original code from "return nElems;" to "return lowerBound;", then you have not understood your find() method fully. I suggest you start a tutorial on the basics of Java first.
This forum is here to help you. It is not here to deliver spoon-feed code or do your assignment for you fully for free.Comment
Comment