# doubt in binary search.....

Ganeshkumar cheekati
Ranch Hand
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........

M Srilatha
Ranch Hand
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!

Ganeshkumar cheekati
Ranch Hand
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
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
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
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.