Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Cloud/Virtualization forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

binary search method

 
Sonali Sehgal
Ranch Hand
Posts: 75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


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
Marshal
Pie
Posts: 20894
75
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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??).

You are stating one not found but one is already there in the array??
 
Henry Wong
author
Marshal
Pie
Posts: 20894
75
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

You are stating one not found but one is already there in the array??


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
Posts: 75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Pie
Posts: 20894
75
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 24
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:

 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic