This week's book giveaway is in the Servlets forum.
We're giving away four copies of Murach's Java Servlets and JSP and have Joel Murach on-line!
See this thread for details.
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes doubt in binary search..... Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "doubt in binary search....." Watch "doubt in binary search....." New topic
Author

doubt in binary search.....

Ganeshkumar cheekati
Ranch Hand

Joined: Oct 13, 2008
Posts: 362


output is:

gani giri gopi geethika
________________________

after sorting using sort method:

gani geethika giri gopi

giri is:2

after sorting using comparator:

gopi giri geethika gani

geethika is:-1

___________________________

geethika is 2.


my doubt is if i am searching the array wioth out passing the comparator then the resulet is incorrect.

it can use -(insertion point)-1 to give the result?


here geethika is:-1...

how i got -1 value in output........








SCJP5 and SCWCD1.5
Think Twice Act Wise...
M Srilatha
Ranch Hand

Joined: Aug 27, 2008
Posts: 137
Hi,

because you have used Comparator1 for sorting,you have to use the overloaded version of binarySearch() method which takes Comparator object to search for an element. Otherwise results are not predictable.
Here in this example, it was not able to find "geethika" because the method will think that the sorting is done in alphabetical order where the array was sorted in reverse order. And when it doesnt find the element for which you are searching, it will return -(insertion_point)-1. Here in this example, its -0-1 which is -1.

Hope this helps!


Thanks,<br />Srilatha M
Ganeshkumar cheekati
Ranch Hand

Joined: Oct 13, 2008
Posts: 362
hi..

if i am using another element("gani","giri") instead of "geethika" in case of not passing comparator it is giving same output as -1..

do you mean it is not finding that element while searching...?
M Srilatha
Ranch Hand

Joined: Aug 27, 2008
Posts: 137
HI,

I dont know whether you are aware of binarySearch algorithm.
Let me explain:
if you have the array a1 with following elements:
gopi giri geethika gani

And say you are searching for "gani".
The size of the array is 4 here. first it will calucalte mid = (low+high)/2
Here it will be 1 { (0+3)/2 }. Then it will for check a1[mid] which is "giri".
And compares with "gani". As per string comparison, "gani" will come before "giri" so it tries to search the first half of the array and ends in no match found. "gani" cab be inserted at index 0 to keep the array sorted so the method will return -1 (-0-1) as result!

If we are searching for "gopi", as "gopi" will come after "giri" (alphabetical order), it will search the second half of the array and ends in no match found. And the result will be -5 (-4-1).

Hope you will get it!
Ganeshkumar cheekati
Ranch Hand

Joined: Oct 13, 2008
Posts: 362
In case of "gopi" it search in second half of the array and not found..

why -4-1=-5....? is 4 insertion order?

M Srilatha
Ranch Hand

Joined: Aug 27, 2008
Posts: 137
because it doesnt find that in the second half of the array, that can be added to the end of the array i.e. insertion point will be 4. So the result is -4-1 = -5!
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: doubt in binary search.....
 
Similar Threads
Please explain the code.
K&B BOOK PAGE NUMBER(558)
Doubt in binarySearch
sorting array
Doubt in Collections