binary search on character array in java

Question

I want to know how to do binary search on character array in java

There is a in-build function in java , but i don't want to use that , any help or pointers will be really appreciated.

I just started with below as i know binary search needs the array to be sorted

char[] whitelist = {'f','e','d','c','b','a'};

                Arrays.sort(whitelist);

                for (char ch : whitelist) {  
                    System.out.println("The values after sorting\n"+ch);
                }

I doubt that you really need help with google or SO's search functionality. — Andreas Dolk
– Andreas Dolk, Commented Sep 20, 2011 at 6:00
If the array is sorted then you dont need to actually "search" it, if you want "f" then just count how far away f is from a and access the index of the whitelist at that position. — rapadura
– rapadura, Commented Sep 20, 2011 at 6:01
AntonioP I'm guessing he wants a system that will work even when he's not just spelling out the whole alphabet. :) — Owen
– Owen, Commented Sep 20, 2011 at 6:04

Saket · Accepted Answer · 2011-09-20 06:55:05Z

3

As simple as Java does:

int binarySearch(char[] a, char key) {
    int low = 0;
    int high = a.length - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        char midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

Of course, replace the array a with your array, i.e. whitelist.

Basically, look out for this - http://en.wikipedia.org/wiki/Binary_search_algorithm#Iterative

edited Sep 20, 2011 at 6:55

answered Sep 20, 2011 at 6:04

Saket

46.3k13 gold badges65 silver badges80 bronze badges

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

7 Comments

Roland Illig Over a year ago

Especially for beginners it's good style to have properly indented code.

Saket Over a year ago

@kobe - No problems. This should work, since this is pretty much what is done by the in-built API as well. Generally, if you intend to implement an API on your own, it is good to see (in fact, leverage) the in-built API's source itself, to start with.

Stephen C Over a year ago

@Saket - this is HOMEWORK. It is bad form to provide a potted answer that the OP can simply copy and paste ... as he is apparently doing. The point of homework is to get the student to do the work, and learn in the process. Giving him/her potted answers defeats the purpose.

Andreas Dolk Over a year ago

(this is more or less copy/pasted from Arrays#binarySearch0)

kobe Over a year ago

@StephenC ,@andreas , I went through the logic and understood now , as you suggested i won't copy as it is.

|

Collectives™ on Stack Overflow

binary search on character array in java

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related