Hey guys, I'm trying to program which finds the closest value stored in a sorted array using binary search. In other words, it should read the middle array and then move to the middle of the half where this value should be (unless the closest value is in the middle already). Anyway, my program doesn't seem to be working properly and i'm getting a bit frustrated, could you possibly push me in the right direction?

so for example, this is my array

data[] = ( 2.53 3.24 4.71 7.35 7.58 7.89 9.83 12.03 19.4 23.08 4.5 )

and when I say i want to find a value closest to 4.5, it should say that its stored in data [2] but I get data[6] for some reason

Thanks :)

public static int binary (double [] data, int a,int b, double elem)
     { // start binary
    
    int left = a;
    int right = b;

   
     
    while ( left < right)
     {
    

    int middle = (left+right)/2;
    double i = Math.abs(data [middle]- elem);
    double j = Math.abs(data [middle+1]- elem);
    double k = Math.abs(data [middle-1]- elem);

    if (k > i && j > i)
    
    return middle;
    
    else if ( k < i && k < j)
    
    left = middle - 1;

    
    else if ( j < i && j < k)
    
    right = middle+1;
    
 
    } 
    
   return left; //The program should always find a closest value but a return statement is required 
                // or what?
}

Recommended Answers

All 13 Replies

The 4.5 at the end of the array means it's not sorted that can't help...

The 4.5 at the end of the array means it's not sorted that can't help...

aah sorry, i forgot to mention that I have two boundaries and right now its set between 0 and 9. that is only data [0-9] are sorted and i only want to use binary search in those locations

so a = 0 and b = 9 in this case

OK.
Put a load of print statements into your code, printing the values of the key variables at each stage so you cen see where it's going wrong, eg at line 11 print left and right.

Suppose you are looking at a range of values between the indexes "left" and "right." You look at a value in the middle of the range and decide that you want to move left -- the to the left of the middle are closer to the target value that you're searching for. To do this, should you change the value in the "left" variable or the value in the "right" variable?

(Sometimes the most immediately intuitive answer is not the correct answer. ;-)

commented: Very helpful and helps the OP think in the right direction without just giving the answer +14

Print statements can help. Using a debugger can help. With a debugger, you can step through the code as it executes and see where it's behavior diverges from what you expect it to do.

Print statements can help. Using a debugger can help. With a debugger, you can step through the code as it executes and see where it's behavior diverges from what you expect it to do.

Yes, I agree. But when working with beginners I tend to advise print because they are already familiar with it, plus mostly they are not using an IDE yet. Debuggers are better, but there are different debuggers in every IDE, and they all have significant learning curves.

alright thanks for the tip! now it appears that this method is not using the sorted array, but the unsorted one. why is that? once i've changed the memory locations shouldn't they hold throughout the programme? in my main method i execute the programme in such an order that the array is sorted before i run the binary search

Yes, the method will operate on whatever data array you have passed it.

Yes, the method will operate on whatever data array you have passed it.

ok but how do i make it run the new (sorted) array?

haha sorry i made a very silly mistake in my main method, thanks for all the help guys :)

With the changes to the way 'left' and 'right' are updated, I was quite surprised to find that it worked quite well for me. I threw a large number of test cases at it, and I found...

  1. It's not very consistent about handling values that are exactly at the mid-point between two given values in the sorted array.
  2. For some of those values, it goes into an infinate loop.

Have fun!

(And if you have any further questions, please feel free to ask. ;-)

With the changes to the way 'left' and 'right' are updated, I was quite surprised to find that it worked quite well for me. I threw a large number of test cases at it, and I found...

  1. It's not very consistent about handling values that are exactly at the mid-point between two given values in the sorted array.
  2. For some of those values, it goes into an infinate loop.

Have fun!

(And if you have any further questions, please feel free to ask. ;-)

oh yea that code is quite old now, i have changed it and i made a intentional mistakes there which i had changed to desperately see if i my logic was wrong :P

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.