• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Junilu Lacar
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Knute Snortum
  • Devaka Cooray
  • Tim Cooke
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Ron McLeod
  • Carey Brown
Bartenders:
  • Paweł Baczyński
  • Piet Souris
  • Vijitha Kumara

Help me with my Binary Search conquest

 
Ranch Hand
Posts: 55
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm digging deep here. Here is my class with the Binary Search method components in it:

The output is this:
Initial Middle Index = [3]

Round 1, sortedNums[middle] < searchInt:
Current firstIndex = [4], with a value of 8,
Current lastIndex = [7], with a value of 14.
New Middle Index = [5], with a value of 9
Remaining Array Half:
8,
Round 2, sortedNums[middle] < searchInt:
Current firstIndex = [6], with a value of 11,
Current lastIndex = [7], with a value of 14.
New Middle Index = [6], with a value of 11
Remaining Array Half:
We found 11 at index [6]


My question is, why didn't 8, print out as 8,9,11,14 instead?
 
Sheriff
Posts: 6363
172
Eclipse IDE Postgres Database VI Editor Chrome Java Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't know what the for-loops at lines 49 and 55 are supposed to do, but I don't think they're correct.
 
Rancher
Posts: 3523
33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The code is missing some parts.  The variable: searchInt used on line 9 is not defined.
 
Sam Peterson
Ranch Hand
Posts: 55
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Norm Radder wrote:The code is missing some parts.  The variable: searchInt used on line 9 is not defined.


You're right, searchInt should have global scope.

Knute Snortum wrote:I don't know what the for-loops at lines 49 and 55 are supposed to do, but I don't think they're correct.


On the first round, we should be seeing output from for loop on line 49 of 8,9,11,14,
 
Norm Radder
Rancher
Posts: 3523
33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Remaining Array Half:
8,


Is that the part that is the problem?  How are you trying to debug the printRemainingNums method to see why it only prints that one number?
 
Knute Snortum
Sheriff
Posts: 6363
172
Eclipse IDE Postgres Database VI Editor Chrome Java Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Sam Peterson wrote:On the first round, we should be seeing output from for loop on line 49 of 8,9,11,14,


But that's not what this for-loop says to do.
 
Norm Radder
Rancher
Posts: 3523
33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If I were to have written this code, I would have added the shown comments (lines 3 and 11) before writing it:

Do the loops on lines 4 and 12 do what the comments ask for?
 
Sam Peterson
Ranch Hand
Posts: 55
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Norm Radder wrote:Do the loops on lines 4 and 12 do what the comments ask for?


Now they do. I had to make the middle, firstIndex, and lastIndex variables global so that the changes done to them in the intBinarySearch method would be visible to the other methods.
I also made the appropriate changes to the for loop declarations in the printRemainingNums method:

Output:
Initial Middle Index = [3]

Round 1, sortedNums[middle] < searchInt:
Current firstIndex = [4], with a value of 8,
Current lastIndex = [7], with a value of 14.
[4] + [7] / 2 = a new middle index of [5], whose value is 9
Remaining Array Half:
8, 9, 11, 14,
Round 2, sortedNums[middle] < searchInt:
Current firstIndex = [6], with a value of 11,
Current lastIndex = [7], with a value of 14.
[6] + [7] / 2 = a new middle index of [6], whose value is 11
Remaining Array Half:
We found 11 at index [6]
 
Norm Radder
Rancher
Posts: 3523
33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The loops on lines  52 and 59 look identical.  What is the purpose of the if statements if the results are to do the same thing?

What should happen when searchInt is 3?
 
Sam Peterson
Ranch Hand
Posts: 55
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Norm Radder wrote:The loops on lines  52 and 59 look identical.  What is the purpose of the if statements if the results are to do the same thing?

What should happen when searchInt is 3?


See for yourself. Change line 12 from to , and observe the output.

Edit: using a value of 2 instead of 3 forces the program to go through two rounds, and better demonstrates the functionality of the program.
 
Norm Radder
Rancher
Posts: 3523
33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There is often a difference between "what should happen" and what actually happens when the code is executed.
I was asking for what you expect to see printed.  Not what the code currently does.

What is the purpose of the if statements if the results are to do the same thing?
 
Sam Peterson
Ranch Hand
Posts: 55
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Norm Radder wrote:What is the purpose of the if statements if the results are to do the same thing?


You're right. The intBinarySearch method already does all of the work for us by updating the middle, firstIndex, and lastIndex variables, so iterating through the remaining sortedNums is as straight forward as . Thanks for pointing that out.
 
Ever since I found this suit I've felt strange new needs. And a tiny ad:
Java file APIs (DOC, XLS, PDF, and many more)
https://products.aspose.com/total/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!