• 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
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

doubt in binary search.....

 
Ranch Hand
Posts: 362
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


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........






 
Ranch Hand
Posts: 137
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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!
 
Those who dance are thought mad by those who hear not the music. This tiny ad plays the bagpipes:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic