• 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
  • Ron McLeod
  • Rob Spoor
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Henry Wong
  • Liutauras Vilda
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Tim Holloway
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Mikalai Zaikin
  • Piet Souris

binarySearch() method of Arrays

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

gives the output-

four one three two
1
two three one four
2


At line1, we have a sorted array of strings 'sa'. Then at line2, why the overloaded version of method binarySearch() is needed which takes a Comparator as an argument? Why the 'two argument' version of this method doesn't work here and gives unpredictable output?
 
Bartender
Posts: 1558
5
Eclipse IDE Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Astha Sharma,

I assume you've understood all 4 lines of output. If yes, then the questions are quite straightforward.

Astha Sharma wrote:Then at line2, why the overloaded version of method binarySearch() is needed which takes a Comparator as an argument?


This is because, at line no. 16 of your snippet, you've sorted the array as per your own comparator (which sorts array in reverse order). Now, when you perform a binary search, the default logic (i.e. 2 arg method) assumes that array is sorted by default order (e.g. alphabetically in case of String etc.) and will try to search the array, but as we know that the array is not sorted as per default ordering, but as per ReverseSort ordering.
So, there should be a way to tell binary search algorithm that by what logic the array is sorted, then only it will be able to search the array properly. Otherwise, it would assume that array is sorted with default logic, and will give 'unpredictable result'.

I hope this helps.

By the way, you can get more info about questions like this by simply looking at JavaDoc of class/method.
 
Ranch Hand
Posts: 144
MySQL Database Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

At line1, we have a sorted array of strings 'sa'.


//line 1: Searches the specified array (sa) for the specified object (rs) using the binary search algorithm.

Then at line2, why the overloaded version of method binarySearch() is needed which takes a Comparator as an argument?


Its the logic whoever wrote the program !! The following method is used

//line 2: Method Signature: public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)
The array to be searched is sa
key the value to be searched for is one
c the comparator by which array is ordered (rs). (which is why comparator argument is used)

CompareTo comparison is based on the Unicode value of each character in the strings.

The result is a negative integer if this String object lexicographically precedes the argument string.
The result is a positive integer if this String object lexicographically follows the argument string.
The result is zero if the strings are equal; compareTo returns 0 exactly when the equals(Object) method would return true.

lexicographic ordering: If two strings are different, then either they have different characters at some index that is a valid index for both strings, or their lengths are different, or both.

Why the 'two argument' version of this method doesn't work here and gives unpredictable output?


Arrays.binarySearch is producing the right results. I do not see any un-expected results.
sa has sa[0] = four, sa[1] = one, sa[2] = three, sa[3]= two and for overloaded binarySearch method right output is produced.
 
Astha Sharma
Ranch Hand
Posts: 250
Android Eclipse IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Anayonkar Shivalkar and Zeeshan Sheikh for the explanation.
I was not considering that it's "Binary Search". It would not need the Comparator as argument it it would be method performing linear search and I was thinking of it as lenier search algorithm, thats why got confused. My mistake
 
Yup, yup, yup. Tiny ad:
Thread Boost feature
https://coderanch.com/t/674455/Thread-Boost-feature
reply
    Bookmark Topic Watch Topic
  • New Topic