• 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 binarySearch

 
Ranch Hand
Posts: 182
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
HI
In Arrays.binarySearch how can we predict the output for an unsucessful search.I am reading K&S book but I didn't get the point.
Can anyone explain me. Thanks in advance
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The JavaDocs is always a good place to look stuff up...

http://java.sun.com/j2se/1.5.0/docs/api/java/util/Arrays.html

From the Java Doc...

Note that this guarantees that the return value will be >= 0 if and only if the key is found.



Hence, if the return value is negative, the result was not found.

Henry
 
Ranch Hand
Posts: 952
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Arrays.binarySearch(Array,key); only works on sorted array. If you search on unsorted array than it will give you undefined result.

 
Balaji Bang
Ranch Hand
Posts: 182
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
In K&S Book it is given about unsuccessful Search like this .........

[[[[[[Unsuccessful searches return an int index that represents the insertion point.
The insertion point is the place in the collection/array where the element
would be inserted to keep the collection/array properly sorted. Because positive return values and 0 indicate successful searches, the binarySearch()
method uses negative numbers to indicate insertion points. Since 0 is a valid
result for a successful search, the first available insertion point is -1. Therefore,
the actual insertion point is represented as (-(insertion point) -1). For
instance, if the insertion point of a search is at element 2, the actual insertion
point returned will be -3.]]]]]

And in this I didn't get the formula .. (-(insertion point) -1). What it says. And I tried the following unsuccessful Searches....
Can you tell me how the above point can be related to this output ???


import java.util.*;
public class Ex {
public static void main(String [] args) {
String [] sa = {"one", "two", "three", "four"};
Arrays.sort(sa); // #1
for(String s : sa)
System.out.print(s + " ");

System.out.print("\nfive = "
+ Arrays.binarySearch(sa,"five")); // result -1
System.out.print("\nsix = "
+ Arrays.binarySearch(sa,"six")); // result -3
System.out.print("\nseven = "
+ Arrays.binarySearch(sa,"seven")); // result -3
System.out.print("\nhex = "
+ Arrays.binarySearch(sa,"hex")); //result -2
}
}
 
Punit Singh
Ranch Hand
Posts: 952
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
String [] sa = {"one", "two", "three", "four"};
Arrays.sort(sa); // #1

after sorting sa will become:
sa=[four, one, three, two], sorted by alphabetical order.

So if any key you want to find not in the list can be added at these positions



Output will give you these index by converting in negative and deducting 1 so:






 
Ranch Hand
Posts: 580
Eclipse IDE
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think we can say that,when a element(X) is not found,then the method would find a place(index) where X can be inserted and it would return a value.
And the value is :-
inverting the index value(i.e to + to - ) and then substracting 1 from it.

Ex: if the position to be inserted is 4, then -4 -1= -5 would be returned.
 
Punit Singh
Ranch Hand
Posts: 952
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes you are right James.
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic