This week's book giveaway is in the Artificial Intelligence and Machine Learning forum.
We're giving away four copies of TensorFlow 2.0 in Action and have Thushan Ganegedara on-line!
See this thread for details.
Win a copy of TensorFlow 2.0 in Action this week in the Artificial Intelligence and Machine Learning forum!
  • 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Paul Clapham
  • Bear Bibeault
  • Jeanne Boyarsky
Sheriffs:
  • Ron McLeod
  • Tim Cooke
  • Devaka Cooray
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Jj Roberts
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • salvin francis
  • Scott Selikoff
  • fred rosenberger

Confused about binary search

 
Ranch Hand
Posts: 161
1
jQuery Eclipse IDE
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi All,

I am confused about the output of the program given below



The above program is from enthuware. The answer is anything between -5 to 3. Why the answer is from -5 to 3.

Thanks & Regards,

Swapna
 
Master Rancher
Posts: 3701
44
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
From the Arrays API

Returns:
index of the search key, if it is contained in the array within the specified range; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element in the range greater than the key, or toIndex if all elements in the range 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.



So, if an item is found in the array, it could be found at position 0, 1, 2, or 3.

If an item is not found, then we need to know where it would be inserted, if you were inserting.  That would be at position 0 (before the current 0), 1, 2, 3 (before the current 3), or 4 (after the current 3).  Since the return value is supposed to be returnValue = (-insertionPoint - 1), those insertion points of 0, 1, 2, 3, 4 get transformed into -1, -2, -3, -4, -5 respectively.
 
Swapna latha
Ranch Hand
Posts: 161
1
jQuery Eclipse IDE
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thats correct. But question is that search will be placed at 4th position right

Mike Simmons wrote:From the Arrays API

Returns:
index of the search key, if it is contained in the array within the specified range; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element in the range greater than the key, or toIndex if all elements in the range 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.



So, if an item is found in the array, it could be found at position 0, 1, 2, or 3.

If an item is not found, then we need to know where it would be inserted, if you were inserting.  That would be at position 0 (before the current 0), 1, 2, 3 (before the current 3), or 4 (after the current 3).  Since the return value is supposed to be returnValue = (-insertionPoint - 1), those insertion points of 0, 1, 2, 3, 4 get transformed into -1, -2, -3, -4, -5 respectively.

 
Sheriff
Posts: 9674
42
Android Google Web Toolkit Hibernate IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If the element should be at the first place in the array (which means it is smaller than all elements in the array) i.e. at index 0, you'll get -1 as result (as it can't return you -0 as there is no -0). If the element should be at the 1st index of the array, you'll get -2 and so on. So if the element should be at the last of the array i.e. it is greater than all the elements of the array, you'll get -(array.length + 1). Length of your array is 4, so you'll get -5 in that case. Since the element is greater than all the elements in the array, it should be placed at 5th index of the array which doesn't exist.
 
Swapna latha
Ranch Hand
Posts: 161
1
jQuery Eclipse IDE
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Ankit, I got the point, but when i executed the program the result shown was -1. Not sure why it was -1.

Ankit Garg wrote:If the element should be at the first place in the array (which means it is smaller than all elements in the array) i.e. at index 0, you'll get -1 as result (as it can't return you -0 as there is no -0). If the element should be at the 1st index of the array, you'll get -2 and so on. So if the element should be at the last of the array i.e. it is greater than all the elements of the array, you'll get -(array.length + 1). Length of your array is 4, so you'll get -5 in that case. Since the element is greater than all the elements in the array, it should be placed at 5th index of the array which doesn't exist.

 
Marshal
Posts: 25965
70
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Swapna latha wrote:Hi Ankit, I got the point, but when i executed the program the result shown was -1. Not sure why it was -1.



You didn't say what you passed in as the parameters of that code. But assuming that you didn't, then the code is trying to find the location of "" in the array. Now "" isn't in the array but it would go before the first entry. So... that's -1, isn't it?
 
brevity is the soul of wit - shakepeare. Tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
reply
    Bookmark Topic Watch Topic
  • New Topic