• 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

Arrays BinarySearch

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

We see that the array is not sorted. But instead of giving a negative value, the output comes as 2. What is the reason behind the output. Why is the first "c" getting ignored?
 
author and iconoclast
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
By definition, the result is bogus if the input array is not sorted. But you can look at it and understand where the bogus result comes from, if you like.

Binary search works by looking at the center element of the array and deciding whether the search target would be before or after that element. The array is then divided in half. Since the array is assumed to be sorted, one half should contain all the elements that come after that center element, and the other half all the ones that come before it. The half that the target might be in is examined further; the other half is ignored. Therefore, the algorithm sees "b", decides that "c" must come after that, and completely ignores the first half of the array where the first "c" appears.
 
Ranch Hand
Posts: 338
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Binary search works by looking at the center element of the array


Is there any way to find what is the center element's value during binary search.
Suppose

Here is there any built-in method in Arrays class to find out the center element .
Regards.
 
ramya narayanan
Ranch Hand
Posts: 338
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Two points to consider

Then output comes as -2 why?

Then output comes as 0. Why?
How the sorting is done here?
Regards.
 
Marshal
Posts: 79180
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Question 1: The answer is in the ,%20java.lang.Object)]API documentation.
Question 2: You can easily answer that yourself.
 
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
if you follow the logic Ernest laid out, you can see that in the first case, it will conclude that 'c' is not in the array.

and in the second case, it returns the correct answer, so I don't understand your question. Where is the confusion?

and finally, when you say "How the sorting is done here?" - a binarySearch is searching, not sorting. The binarySearch assumes the sorting has ALREADY BEEN DONE. So the actual answer to your question is "It isn't."
 
Yeah, but does being a ninja come with a dental plan? And what about this tiny ad?
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic