Hi,

I want to do line by line calculation of the running tie of following algorithm. I know it would be log N. However, before this I want to understand one statement:

int midIndex = (endIndex - startIndex / 2) + startIndex; //problem statement

If: endIndex = 10

startIndex = 0

then midIndex = 10


which is not correct. Somebody please guide me.


The algorithm is given below:

public int logarithmic(Integer[] data, int key) {
  int startIndex = 0;
  int endIndex = data.length - 1;
  while (startIndex < endIndex) {
   int midIndex = (endIndex - startIndex / 2) + startIndex;
   int midValue = data[midIndex];
   if (key > midValue) {
    startIndex = midIndex++;
   } else if (key < midValue) {
    endIndex = midIndex - 1;
   } else {
    return midIndex;
   }
  }
  return -1;
}

Which I got from:http://www.mcs.csueastbay.edu/~bhecker/Previous Terms/CS-3240-Sum14/Examples/BigOExamples.java

I would discuss about the line by line generation of running time afterwards. Some body please guide me about the problem statement above.

Zulfi.

 

Do you understand how binary search works?

In words, given a starting index and an ending index, what should the middle index be?

Given what you want it to represent, can you figure out an equation to arrive at it?

 

Hi,
Thanks for your response. Actually I am not interested in developing in the eq. Equation is already provided in line#5 of the above code. I have a feeling that its not correct. This is what I want to know.

If: endIndex = 10
startIndex = 0
then midIndex = 10
which is not correct.

Kindly guide me if the line # 5 is correct or not.

Zulfi.

 

Hi,
Thanks for your response. Actually I am not interested in developing in the eq. Equation is already provided in line#5 of the above code. I have a feeling that its not correct. This is what I want to know.

If: endIndex = 10
startIndex = 0
then midIndex = 10
which is not correct.

Kindly guide me if the line # 5 is correct or not.

Zulfi.

If you can't figure out how to find the midpoint of two indices, how do you ever plan to ever write a program of any kind that does anything useful?

By saying that you are not interested in developing the equation you need, even if only to check the correctness of an equations you suspect, you are just saying that you expect everyone else to spoon feed you every thing for every program you ever hope to write. What's the point?

 

You should first learn operator precedence. Then figure out what the result SHOULD be. Finally, walk through that line to understand what it is doing.

And, I agree with WBahn, you should be able to write the code by knowing what it is supposed to do. It's really not that hard.

 

Hi,
Thanks for your reply.

If you can't figure out how to find the midpoint of two indices, how do you ever plan to ever write a program of any kind that does anything useful?

Unbelievable.

By saying that you are not interested in developing the equation you need, even if only to check the correctness of an equations you suspect, you are just saying that you expect everyone else to spoon feed you every thing for every program you ever hope to write. What's the point?

Why should i reinvent the wheel?

You should first learn operator precedence. Then figure out what the result SHOULD be. Finally, walk through that line to understand what it is doing.

int midIndex = (endIndex - startIndex / 2) + startIndex;
int midIndex = (10-0 /2) +0;
int midIndex = (10-0) +0;// division has more precedence over subtraction
int midindex = 10;

I did the trace. i didnt get the correct answer. Some body please guide me.
Its not possible for everybody to know everything. if you are telling some body something on this forum, its not spoon feeding. This is the purpose of forum.
I have shown you my work. If you can think the correct answer, please guide me. Otherwise you dont have to say anything.

Zulfi.

 

I agree, unbelievable. But not the way you meant it. You aren't "reinventing the wheel", you are learning how a wheel works. Do you think a person learning autorepair doesn't need to know how an engine works? And this sort of thing is a baby step. If you aren't willing to figure things like this out, I fear you won't get very far.

What you didn't do was figure out what the answer should be. Hint, the variable is well named.

 

I agree, unbelievable. But not the way you meant it. You aren't "reinventing the wheel", you are learning how a wheel works. Do you think a person learning autorepair doesn't need to know how an engine works? And this sort of thing is a baby step. If you aren't willing to figure things like this out, I fear you won't get very far.

What you didn't do was figure out what the answer should be. Hint, the variable is well named.

 

Hi,
It should be 5. But how its 5. One reason is the precedence which I have shown that division has more precedence over subtraction. Other thing can be that the equation is not correct for which I posted this. But I still cant get answer to my question that the equation is correct or not? First tell me this.

Zulfi.

 

How did YOU get that the answer should be 5? Did you ask someone else who told you that, or did you come to that answer yourself. If the latter, how did you do it. Show the math steps you took to do it.

 

Hi,

How did YOU get that the answer should be 5?

Based upon the hint provided by Philba:

Hint, the variable is well named.

But I cant evaluate it to be 5. That's why I am asking whether the statement is correct or not? No body has replied me yet.

Show the math steps you took to do it.

Okay I am showing it again:
int midIndex = (endIndex - startIndex / 2) + startIndex;
int midIndex = (10-0 /2) +0;
int midIndex = (10-0) +0;// division has more precedence over subtraction
int midindex = 10;

Please guide me if the statement is correct or not.

Zulfi.

 

Based upon the hint provided by Philba:

So someone tells you that the variable midIndex is well named and it just comes to you that the value must be 5?

The value of startIndex and endIndex don't come into it at all?

So if startIndex had been 20 and endIndex had been 50, you would have still said midIndex, since it is well named, must be 5?

Or would you have come up with a different value?

If so, what value and how would you have come up with?

Forget about some line of code that you didn't write and that you just copied from someplace.

Come up with YOUR OWN equation based on YOUR ability to figure out what midIndex should be!

 

Hi,
<Come up with YOUR OWN equation based on YOUR ability to figure out what midIndex should be!>
Why? Reinvent the wheel.
Thanks for your response. I got this problem solved on other forum in just 5 minutes after posting. I repeatedly asked whether the statement is correct or not but I didnt get any reply. However I got quick response that the statement was not correct. I think your approach is not good. You should not hide the truth. Again its a diversion which completely confused me.

Zulfi.

 

Hi,
<Come up with YOUR OWN equation based on YOUR ability to figure out what midIndex should be!>
Why? Reinvent the wheel.

Then why ask how to solve any of the questions you ask about? You haven't asked one yet that others haven't solved countless times. So why should you even be interested since it's just reinventing the wheel?

Thanks for your response. I got this problem solved on other forum in just 5 minutes after posting. I repeatedly asked whether the statement is correct or not but I didnt get any reply. However I got quick response that the statement was not correct. I think your approach is not good. You should not hide the truth. Again its a diversion which completely confused me.

Zulfi.

Then why are you still asking about it and why can you still not see how to fix it? You are wanting someone else to tell you exactly what to change so that you can "fix" it without gaining ANY understanding as to why the current version is wrong or why the modified version is right. If you won't put for the effort now, why should any potential employer expect you to put forth the effort ever?

If asking you how to find the midpoint of two numbers completely confuses you, then you have much more serious problems to worry about.

If you are asked in an interview (and it's a common interview question) to describe how binary search works or to write a program on paper to implement it, what are you going to tell them? "Oh, sorry, that's a solved problem and I don't reinvent wheels. Can you just tell me what my starting salary will be?" Though I'm pretty sure they will have an answer all ready for you.