• 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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • Devaka Cooray
  • Ron McLeod
  • Jeanne Boyarsky
Sheriffs:
  • Liutauras Vilda
  • paul wheaton
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Piet Souris
  • Carey Brown
  • Tim Holloway
Bartenders:
  • Martijn Verburg
  • Frits Walraven
  • Himai Minh

Question on Collections.binarySearch()

 
Ranch Hand
Posts: 30
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
import java.util.*;

public class UText {
public static void main(String args[]) {
List<String> st = new LinkedList<String>();
st.add("five");
st.add("six");
st.add("seven"); //eight , five , seven , six
st.add("eight");
//Collections.sort((List<String>) st);
System.out.println(Collections.binarySearch((List<String>) st, "nine"));
}

for the above examples i have following questions
1.The output is -2 can someone explain how to find this value
2.If i run using System.out.println(Collections.binarySearch((List<String>) st, "ten")); the output is -5
3.I remember before perfoming binary search the values has to be sorted otherwise you get undefined value.
//First case no sort
System.out.println(Collections.binarySearch((List<String>) st, "six"));
Returns 1 --- Should n't I get the undefined value
//Second case uncomment sort and run - Sorted and searched
Collections.sort((List<String>) st);
System.out.println(Collections.binarySearch((List<String>) st, "six"));
Returns 3


Appreciate your reply.
 
Sheriff
Posts: 27451
88
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
"Thiyagu", please check your private messages regarding an important administrative matter.

Thank you.
 
Ranch Hand
Posts: 537
Eclipse IDE Python Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well to do a search, the list has to be sorted. If the search is successful then the search returns the index of the searched value. If its not successful then it returns -insertion point - 1. Means where the searched value has to go. Also when you do collection.sort on strings, they are sorted based on alphabetical values(Strings implement comparable).
1. If nine was included in the list then it would have been after five. Means insertion point = 2. Therefore -2-1 = -3 (unsuccessful)
2. If ten was included then it would have been after six.Means insertion point = 4. Therefore -5.
3. If the list is not sorted before searching then the results are unpredictable. The result can be anything.
 
Thiyagarajan Kamala
Ranch Hand
Posts: 30
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Nitish ,
Thanks for the reply.
I understood the first point based on your explanation
for 2 - Why not insert after seven why after eight ?.
for 3 It returns 1 based on insertion order correctlyfor many runs.

Could you clarify.
Thanks.
 
Nitish Bangera
Ranch Hand
Posts: 537
Eclipse IDE Python Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sorry not eight...that's a mistake.I have changed it .When you sort the sorted manner is eight , five , seven , six . So if you take ten, then it will always come after six(t after s always). So its -5.

for 3, well the list is sorted for "six" the search will be successful and the where it is found is returned. So the index of "six" is 3. That is what is returned. But if it is not sorted,returning 1 may be true for many runs but not for all won't be true for all runs. If the list is sorted, returning a value is true for all runs till there is something else is added.
 
Sheriff
Posts: 9697
43
Android Google Web Toolkit Hibernate IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thiyagarajan, please Use Code Tags when you post a source code...
 
Thiyagarajan Kamala
Ranch Hand
Posts: 30
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Nitsh,
//eight , five , seven , six
System.out.println(Collections.binarySearch((List<String>) st, "nine"));
This should be after five which is 2 so inserttion order should be -2-1=-3 right

But I get -2 ?.

Thanks again for taking time to posting reply.
 
Nitish Bangera
Ranch Hand
Posts: 537
Eclipse IDE Python Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think you have commented out the collection.sort(st) line.
 
Thiyagarajan Kamala
Ranch Hand
Posts: 30
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I understood how it works if sorted but could not figure out when it is not sorted

for Nine -2 this is because it is inserting after five
for ten -5 here is the doubt why not insert after sever then it should -3-1 =-4
 
Nitish Bangera
Ranch Hand
Posts: 537
Eclipse IDE Python Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well


this gives -3 which is corret. But if Collection.sort(st) is commented then -2 comes or may be some other number also which is unpredictable.

Well for the second doubt. hmm think about it. If you had added ten in the list like st.add("ten") would it appear in between seven and six when the list is sorted.

plus "nine" is not inserted when you do the binarysearch. Its only searched and just gives out where the possible value should have been present if it were a successful search(insertion point) .
 
Ankit Garg
Sheriff
Posts: 9697
43
Android Google Web Toolkit Hibernate IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Thiyagarajan Kamala wrote:I understood how it works if sorted but could not figure out when it is not sorted



You don't need to know this for SCJP. If binarySearch() is called on an unsorted collection (or you used a comparator to sort but not during searching), then you can say that the output is unpredictable (this is mentioned in Chapter 7, Self Test question 16)...
 
There are 29 Knuts in one Sickle, and 17 Sickles make up a Galleon. 42 tiny ads in a knut:
the value of filler advertising in 2021
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic