+ 1

Java/binarySearch

Does it suppose to return index of first occurrence for thr binarySearch method? What is the problem with this code? It returns the 2 for 5 int arr [] = {3,5,6,9,10,6}; Arrays.sort(arr); System.out.println (arr, 5);

4th Mar 2020, 3:36 PM
MUHAMMED AYDIN
MUHAMMED AYDIN - avatar
13 Answers
+ 3
MUHAMMED AYDIN It is true that the method returns the index of first occurence. But the algorithm works not linear. If you study the example in the binary search lesson you will understand it.
4th Mar 2020, 5:02 PM
Denise Roßberg
Denise Roßberg - avatar
+ 2
Yes it return index where the input found... In your case, It returns 1 not 2, since index starts from 0.. Where is code?
4th Mar 2020, 3:41 PM
Jayakrishna 🇮🇳
+ 2
Hello MUHAMMED AYDIN Please share your complete code. Thanks.
4th Mar 2020, 4:16 PM
Denise Roßberg
Denise Roßberg - avatar
+ 2
MUHAMMED AYDIN It shows me 1 as output which is correct. after sorting: 3, 5, 6, 6, 9, 10 index starts with 0. So 5 is at index 1.
4th Mar 2020, 4:29 PM
Denise Roßberg
Denise Roßberg - avatar
4th Mar 2020, 4:36 PM
Denise Roßberg
Denise Roßberg - avatar
+ 2
MUHAMMED AYDIN I changed the code. Output is 2 which is also correct. https://code.sololearn.com/c3J9v2LwB1Sk/?ref=app after sorting: 3, 5, 5, 6, 6, 9, 10 one 5 at 1 and another at 2. It depends on the implementation of binary search if you find the 5 at 1 or 5 at 2. About binary search in general: https://www.sololearn.com/learn/664/?ref=app
4th Mar 2020, 4:53 PM
Denise Roßberg
Denise Roßberg - avatar
+ 2
Binary search method searches key in the array mid position, every time. Since array passed should be in sorted order. So if search not match at mid position, it take search in either left array or in right array iteratively so if elements contains doublicates then no guarantee for index which one picked.. If it not in sorted also, same undefined behavior happens... Check this in above example by running it for 5 by adding more elements same.. Binary search method searches key in the array mid position, If it take linear search, then it return first occurrence. int arr [] = {3,5,5,5,6,6,9,9,10}; Arrays.sort(arr); System.out.println(Arrays.binarySearch(arr, 5)); Run same with adding some more elements, then answer may vary..
4th Mar 2020, 5:02 PM
Jayakrishna 🇮🇳
+ 1
Could you please run the code? I don't know what I am doing wrongly, but I am getting 2 as return
4th Mar 2020, 4:06 PM
MUHAMMED AYDIN
MUHAMMED AYDIN - avatar
+ 1
Where is your code...? How can I run it, without sharing?
4th Mar 2020, 4:17 PM
Jayakrishna 🇮🇳
+ 1
public static void main (String [] args) { int arr [] = {3,5,6,9,10,6}; Arrays.sort(arr); System.out.println (Arrays.binarySearch(arr, 5)); }
4th Mar 2020, 4:21 PM
MUHAMMED AYDIN
MUHAMMED AYDIN - avatar
+ 1
Can you try for this one, I shared the wrong one?. public static void main (String [] args) { int arr [] = {3,5,6,9,10 }; Arrays.sort(arr); System.out.println (Arrays.binarySearch(arr, 5)); }
4th Mar 2020, 4:33 PM
MUHAMMED AYDIN
MUHAMMED AYDIN - avatar
+ 1
I did for this one, sorry one more time public static void main (String [] args) { int arr [] = {3,5,6, 5,9,10,6 }; Arrays.sort(arr); System.out.println (Arrays.binarySearch(arr, 5)); }
4th Mar 2020, 4:39 PM
MUHAMMED AYDIN
MUHAMMED AYDIN - avatar
0
So assuming binarySearch given index of first occurrence is not certain?
4th Mar 2020, 4:55 PM
MUHAMMED AYDIN
MUHAMMED AYDIN - avatar