Win a copy of Programmer's Guide to Java SE 8 Oracle Certified Associate (OCA) this week in the OCAJP forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

confused by collection sorted

 
Dodo Anakin
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
why people say

" The collection/array being searched must be sorted before you can search it "

waiting for explaination

thanks !
 
Chandra Bhatt
Ranch Hand
Posts: 1710
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

It is binarySearch() method of the Collections factory class that you
use to find the object from the collection. Binary search method's
prerequisites is that your array or collection must be sorted.

To see how binary search method works, follow the link:

Binary Search Method


Thanks,
 
Karen Marie
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I know this is old but after reading the Binary Search Algorithm on wikipedia, I'm still unclear on the consequences of not sorting before performing a search as mentioned on page 557 in K&B.

Using the following:

Object[] obj = {"Hello", "Goodbye", "Adios", "Sionara", "Aloha"};
System.out.println(Arrays.binarySearch(obj, "Adios"));

The output is 2 as expected.

Based on what was said, I was expecting it not to be found or something? It does not discuss the consequences.
 
Henry Wong
author
Marshal
Pie
Posts: 21370
84
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Based on what was said, I was expecting it not to be found or something? It does not discuss the consequences.


The consequences is that it *may* not be found. You have an example where it does work. Try seaching for something else.

Henry
 
Karen Marie
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ah. Hello, Goodbye, and Aloha all returned -4. I just got lucky (unlucky) picking Adios.

Thanks. It helps to have an example of what happens when you do things the *wrong* way as much as when you have it the *right* way.
 
Nicholas Jordan
Ranch Hand
Posts: 1282
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
[Karen Marie:]   Thanks. It helps to have an example of what happens when you do things the *wrong* way as much as when you have it the *right* way.

Well, yes - but just try to write a search for Bill Smith from Mule Shoe Arizona in a short dictionary that is not in alphabetical order.

Your example is short and demonstrates the matter effectively. When we discuss large datasets, such demonstrations are not always easy. Dodo Anakin should google for searching in Java to see the vast collection of work that is devoted to sorting, there are in fact searches that will work on unsorted datasets, be they collections or anything that can be searched. I doubt the internet will lean over to be sorted just because a bunch of computer scientists think it should be sorted, but it can be searched even though it is not sorted - so I would like to know who told Dodo that collections have to be sorted.
 
marc weber
Sheriff
Posts: 11343
Java Mac Safari
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
See this thread on binary searching.
 
Henry Wong
author
Marshal
Pie
Posts: 21370
84
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I doubt the internet will lean over to be sorted just because a bunch of computer scientists think it should be sorted, but it can be searched even though it is not sorted - so I would like to know who told Dodo that collections have to be sorted.


Nicholas does make a good point here. This thread has made the assumption that Dodo is referring to the binary search methods of the Collections class. In fact, the original question (post) makes no such references.

Henry
[ November 25, 2007: Message edited by: Henry Wong ]
 
Karen Marie
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
--------------------------------------------------------------------
Nicholas does make a good point here. This thread has made the assumption that Dodo is referring to the binary search methods of the Collections class. In fact, the original question (post) makes no such references.
---------------------------------------------------------------------------


In the original post "The collection/array being searched must be sorted before you can search it " is an exact quote from a bullet point the K&B book pg 557 regarding the binarySearch() method in Arrays and Collections. Searching on that phrase is how I found the thread. I think Dodo had just left out a few details.
 
Nicholas Jordan
Ranch Hand
Posts: 1282
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
[Karen Marie:]   In the original post "The collection/array being searched must be sorted before you can search it " is an exact quote from a bullet point the K&B book pg 557 regarding the binarySearch() method in Arrays and Collections. Searching on that phrase is how I found the thread. I think Dodo had just left out a few details

Well, the original poster stated: waiting for explaination so these investigations can become teflon-on-ice without occasional feedback from needs of original poster, but what is this doing in certification ? This is a beginner or intermediate java question.

[Karen Marie:]   Based on what was said, I was expecting it not to be found or something? It does not discuss the consequences.

I thought about this all week and really, really wanted to do a stochastic scatter search, still may or may not find it and the thing could be tuned to demonstrate that the consequences of not sorting the data set may or may not hinge on prepatory work such as sorting and searches can be done in arbitrary beginner modes if one is willing to accept an 80% reliability of the search, but the real consequence of sorting is that a much faster determinisim of whether the item is in the dataset will be done.

This is discussed in nearly every sorting and searching paper aimed at this level of work. The link marc cites states "sorted in ascending order", but what that does not discuss is that for short-lived lists of a lengthy nature, it may be faster just to walk through the set using whatever search makes sense if you have detailed knowledge of what the application is trying to do and how the data is structured.

Without further requests from original poster, I suggest you re-post in General Computing, this is a General Computing issue of standard computer science: operating systems, applications, hardware, drivers, features, etc. General computer use stuff.
 
Burkhard Hassel
Ranch Hand
Posts: 1274
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Howdy "Dodo Anakin" !

Please have a look into your private messages by clicking the "My Private Messages" link near the top of this page.

Yours,
Bu.
 
Karen Marie
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
what is this doing in certification ? This is a beginner or intermediate java question.


That quote Dodo mentioned was taken from the K&B book written specifically for the purpose of preparing novices for certification by two people who helped create the exam.

Without further requests from original poster, I suggest you re-post in General Computing, this is a General Computing issue of standard computer science: operating systems, applications, hardware, drivers, features, etc. General computer use stuff.


The original poster appears to be long gone but my question was answered. The quote was intended to make a novice like myself aware of what might happen if you search without sorting in simple cases. I also learned from you that the real world there are much more complicated cases which are not so black and white.

However, I have the answer that should prepare me for the questions on the exam which is enough for now. Thanks so much to everyone for their help.
 
Nicholas Jordan
Ranch Hand
Posts: 1282
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I also learned from you that the real world there are much more complicated cases which are not so black and white.

It gets worse, my best suggestion I can give you is try to code a useable application for any real-world activity that interests you. It all scopes in place much better if you do that.

What is K&B, I always hear that term. It is a certification book, obviously, but we get people in the field who can pass scholastics but are totally useless in reality. The certification guides are a dramatic improvement, I just want to see what this one is.
 
Karen Marie
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sun Certified Programmer for Java 5 Study Guide by Kathy Sierra and Bert Bates. It is definitely for people trying learn Java without a ton of experience. They explain concepts very carefully, repeat, and give lots of examples. Excellent book.

The first thing is that, just like college, there is a big difference between those who know enough to score in the upper 90s and those who barely pass. Unfortunately I have heard a lot of people view the certificate itself as the end game and go for the barely passing grade. They memorize facts without spending a lot of time working with the code.

But the certification itself should just be motivation to learn the material really well and practice. I'm in QA so its perfect for me actually. I get a lot of practice in recognizing mistakes in crappy code.

In general its been a lot like learning a "real" language. I spend a ton of time on new words and new rules for grammer. But no matter how well you know the rules, you can't carry on real conversations unless you practice. I have written about 5500 lines of code so far just practicing concepts that are new to me.

Once a person can 'carry on simple conversations' in Java, so-to-speak, there is still a huge gap between that and being able to author a novel. I suppose the next step would be practicing algorithms or something.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic