File APIs for Java Developers Manipulate DOC, XLS, PPT, PDF and many others from your application. http://aspose.com/file-tools
Big Moose Saloon
 Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies Register / Login

binary search method

Sonali Sehgal
Ranch Hand

Joined: Jul 09, 2009
Posts: 75

Output:
four one three two
one =1
now reverse sort
two three one four
one =-1

one = 2

This is a kathy seirra question.Can some please help me understand the last 2 statements of output one=-1 and one=2 how does that come as the output and under what calculation please help me understanding the same and I could not understand the output of line code 4 and 5??
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 20531

50

I could not understand the output of line code 4 and 5??

In line 4, you are sorting with one sort order, and searching with a different sort order. Basically, it is just like searching an unsorted array... and according to the JavaDoc, the results are undefined. A result of -1 means that it believes that the value was not found, and if found, should come before the first element -- which is wrong.

In line 5, that is the correct answer. What is it that you want to know about it?

Henry

Sonali Sehgal
Ranch Hand

Joined: Jul 09, 2009
Posts: 75
Hi Henry,

I could not understand how does the program calculate the line 4 and line of code 5 and gives the output.I mean I want to know how does the calculation goes about in the program.I could understand some bit of it but not all(as to how does -1 and 2 comes as the output??).

Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 20531

50

First of all, do you know what a binary search is? If not, maybe you should start with that... its not very efficient to explain the details of an algorithm within the confines of a forum.

Correct. Not found and not in the array are not the same thing. There are conditions where items are in the array, but the binary search can fail.

Henry

Sonali Sehgal
Ranch Hand

Joined: Jul 09, 2009
Posts: 75
I do understand the explanation Kathy Seirra book gives me:-

It is imporant for you to understand what binarySearch(...) method returns:

public static int binarySearch(Object[] a, Object key)
Searches the specified array for the specified object using the binary search algorithm. The array must be sorted into ascending order according to the natural ordering of its elements (as by Sort(Object[]), above) prior to making this call. If it is not sorted, the results are undefined. (If the array contains elements that are not mutually comparable (for example,strings and integers), it cannot be sorted according to the natural order of its elements, hence results are undefined.) If the array contains multiple elements equal to the specified object, there is no guarantee which one will be found.

Parameters:
a - the array to be searched.
key - the value to be searched for.
Returns:
index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size(), if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

Throws:
ClassCastException - if the search key in not comparable to the elements of the array.

I also understand this:-

If its unsuccessful, it will return the index where the searched object can be inserted so that the list will remain sorted.
So, if the searched object is to be inserted at 2nd position -3 will be returned.
In the above example, the search is unsuccessful and the new String object is to be inserted at the 0th position(spaces come before alphabets).
So you get -1 as the output. Every time, a binary search will return you an int between -(n+1) to n-1 where n is the length.

My question is how does the calculation as comes in the output in the last 2 lines is how does it calculate.I am not able to get a clear message of that. Because in both sorting and reverse sort "one" is already in the array.

Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 20531

50

My question is how does the calculation as comes in the output in the last 2 lines is how does it calculate.I am not able to get a clear message of that. Because in both sorting and reverse sort "one" is already in the array.

But do you understand the algorithm? Because if you understand the algorithm, then you know how the values are calculated.

Please see the link that I provided for an explaining of the binary search algorithm. Or you can revisit your university algorithm class textbook.

Henry
Guillaume Jeudy
Greenhorn

Joined: Jul 27, 2009
Posts: 24
You don't need to understand the algorithm just the expected behavior. The main thing to understand is that:

method has no way of guessing how the array was sorted initially so it will assume that it was sorted using "natural" ordering (in this case the implementation of java.util.Comparable in java.lang.String).

If you are running binarySearch and the sort is unspecified then results are unpredictable (thats why you got -2 in your case). The only way to properly do binarySearch if the array was not sorted with "natural" ordering is to pass the java.util.Comparator implementation that was initially used for sorting such as:

SCJP 1.4 and 6.0, SCJD

I agree. Here's the link: http://aspose.com/file-tools

subject: binary search method