Java utils binary search not finding all values [duplicate]

Question

I am trying to search an array for a value and decided to use the built in binary search to do so. I have a class:

import java.util.*;
public class Charge {
private int isAcct;
private int[] acctNumbers = {5658845,4520125,7895122,8777541,8451277,
1302850,8080152,4562555,5552012,5050552,7824577,
                    1250255,1005231,6545231,3852085,7576651,7881200,
                    4851002};


public Charge(int aNum) {
    isAcct = aNum;
}
public Boolean isValidAcctNumber() {
    int m = Arrays.binarySearch(acctNumbers, isAcct);
    if (m == -1)
        return false;
    else
        return true;
}
}

And a test:

import java.util.Scanner;
public class ChargeTest {
public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    System.out.println("What is your account number?: ");
    int num = scan.nextInt();
    Charge charge = new Charge(num);
    System.out.println(charge.isValidAcctNumber());

    if (charge.isValidAcctNumber() == false) {
        System.out.println("Your account "+num+" is not a valid account");
    } else  {
        System.out.println("Your account "+num+" is a valid account");
    }
}

}

This works for certain numbers like 4851002, but not others like 1302850. I really haven't the foggiest idea why. I will most likely just implement binary search by hand, but I am confused as to why this doesn't work.

You really should read at least part of the docs for binary search before asking a question. — Captain Giraffe
– Captain Giraffe, Commented Apr 23, 2013 at 20:59
JavaDoc clearly states: The array must be sorted. If parts of the JDK misbehave, read it's docs before posting a question. — jlordo
– jlordo, Commented Apr 23, 2013 at 21:01

rgettman · Accepted Answer · 2013-04-23 20:58:13Z

4

Binary search only works on an array that is already sorted.

Quoted from Arrays.binarySearch javadoc:

Searches the specified array of ints for the specified value using the binary search algorithm. The array must be sorted (as by the sort(int[]) method) prior to making this call. If it is not sorted, the results are undefined. If the array contains multiple elements with the specified value, there is no guarantee which one will be found.

If it's not already sorted, then it will not find some numbers.

Sort it before attempting any binary search:

Arrays.sort(acctNumbers);

answered Apr 23, 2013 at 20:58

rgettman

179k30 gold badges282 silver badges365 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Andy Thomas Over a year ago

+1 for a fuller answer than mine, and to make up for the troll who downvoted the correct answers.

Andy Thomas · Accepted Answer · 2013-04-23 20:58:04Z

2

A binary search requires a sorted array.

You could:

Provide the array in sorted order
Or sort it with Arrays.sort()

answered Apr 23, 2013 at 20:58

Andy Thomas

86.8k12 gold badges111 silver badges160 bronze badges

1 Comment

rgettman Over a year ago

+1 to make up for the downvoter who downvoted a correct answer and for suggesting to simply provide the array already sorted.

Captain Giraffe · Accepted Answer · 2013-04-23 21:06:11Z

0

If Java used chaining it would look like

if ( Arrays.sort(acctNumbers).find( number ) )

Now you have to do

List l = Arrays.sort(acctNumbers);
// decide on 
Arrays.binarySearch( l, number );

answered Apr 23, 2013 at 21:06

Captain Giraffe

14.8k7 gold badges42 silver badges69 bronze badges

Collectives™ on Stack Overflow

Java utils binary search not finding all values [duplicate]

3 Answers 3

1 Comment

1 Comment

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

1 Comment

Comments

Linked

Related