Solved

binary search

Posted on 2011-09-30
7
193 Views
Last Modified: 2012-05-12
i wrote my binary search program as below...

char[] c1 = new char[]{'d','a','f','k','e'};
      Arrays.sort(c1);
x = 'f';
binarySearch(c1,x);      
public static int binarySearch(char [] c1, char x)
{  
      int low = 0;
        int high = c1.length - 1;
        int mid;
        while( low <= high )
        {
            mid = ( low + high ) / 2;

            if( c1[ mid ] == x )
                low = mid + 1;
            else if( c1[ mid ] ==  x )
                high = mid - 1;
            else
                return mid;
        }

        return 1000;  
}

I am not getting correct results with the above code


if x = 'f'

return value is 2

even if x = 'q'

return value is 2


what is the mistake

0
Comment
Question by:shragi
  • 3
  • 2
7 Comments
 
LVL 47

Expert Comment

by:for_yan
ID: 36895556
The above works - you should not for
precise equality, instead it should be < or > 
0
 
LVL 13

Accepted Solution

by:
Hugh McCurdy earned 500 total points
ID: 36896213
This looks like homework.

One way to help yourself understand how your program works is to make yourself some "cards" (cut up a piece of paper) and put a letter on each card.  Then go through the program as if you are the computer.

Another is to print out the status of the program along the way.  In Java, you can use System.out.println();

For example  (place right after you set the value of mid)

System.out.println ( "mid = " + mid );
System.out.println ( "c1[mid] = " + c1 [ mid ] );
System.out.println ( "x = " + x );

This way you can see what your program is doing and (hopefully) why it won't work.

If you are still stuck, return here with the output of those println() messages.
0
 
LVL 47

Expert Comment

by:for_yan
ID: 36897249


Shragi, you should change

if( c1[ mid ] == x )

to if(c1[mid] <x)

on its first occurrence
and

to (if(c1[mid] > x)


on its second occurrence,

as you need to determine in what half
your x value lies and based on that
either modify lower or upper boundary

As you understand in case if(c1[med] == x) then you'd rather
return med as the goal of your search (as you do it below).


So those were your two mistakes - replace those
==  by < in the first occurrence and by > in the second - and your code should be fine -
I tested it and it worked for me

_alias99,

shragi posted the whole code and asked to help to pinpoint the mistake
I found two mistakes (or rather one mistake made twice)
and communicated it. I posted the code which was all pasted form shragi's
question with two symbols corrected.
Homework or not, I don't think this interaction violates EE rules, which say:

"helping a student with a project is allowable, but not doing it for them."

The Asker wrote the code himself - it was just help and cannot be qualified as "doing it for them" by any means.
 







0
 
LVL 13

Expert Comment

by:Hugh McCurdy
ID: 36898244
for_yan, I did something similar in C++ and it wasn't OK with the moderator.  I was told that instead of telling the author which line was wrong was to say something like "you can't use a null pointer in C++; can you find the line where you used the null pointer?"  What I had done (wrong) was tell the author that he had a null pointer on line X.
0
 
LVL 47

Expert Comment

by:for_yan
ID: 36908116
I also poseted explanation before - and this is not much of an issue - it was most probably a misprint on the part of the author, just put ==
when he meant > or < - nothing much
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
basic hardware to learn oop advanced design patterns 3 88
Securing Jmx Console and web console 2 65
maven project error 5 48
Java SE 8u111  Lot of stuff broke 11 54
By the end of 1980s, object oriented programming using languages like C++, Simula69 and ObjectPascal gained momentum. It looked like programmers finally found the perfect language. C++ successfully combined the object oriented principles of Simula w…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Down…
Viewers will learn one way to get user input in Java. Introduce the Scanner object: Declare the variable that stores the user input: An example prompting the user for input: Methods you need to invoke in order to properly get  user input:

920 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now