Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 4 of 4

Thread: Binary Search for an array of random ints - Can't find the target value

  1. #1
    Junior Member
    Join Date
    Jan 2012
    Posts
    6
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Binary Search for an array of random ints - Can't find the target value

    Writing a binary search for an array of random ints. When in comes time to pick a target value and search for it, the program will not identify the number. If you run it you'll see what I mean

    /*
    	Exercise4.java
     
    	Binary Search
     
    */
     
     
    import java.io.*;
    import java.util.*;
     
    public class Exercise4
    {
    	private static final int NOT_FOUND = -1; // this value GLOBAL to file - visible in ALL methods in this file
     
    	public static void main( String args[] )
    	{
    		Scanner kbd = new Scanner(System.in);
    		Random rand = new Random();
     
    		if (args.length < 1 )
    		{
    			System.out.println("\n\n      !! You must enter a desired array length on the cmd line !!\n");
    			System.exit(0);
    		}
     
    		int array[] = new int[ Integer.parseInt(args[0]) ];
    		int count=0;
     
            for (int i=0 ; i < array.length ; ++i )
            {
                int r = 1 + rand.nextInt(100);
                if ( binarySearch( array, r ) == NOT_FOUND )
                {
                    insertInOrder( array, count, r  );
                    ++count;
                }
                // else ignore this value its already in the array - no dupes to be inserted
            }
     
    		printArray( array );
     
    		do
    		{
    			System.out.print("number to search for (negative to quit)? ");
    			int target = kbd.nextInt();
    			if (target < 0) break;
     
    			int index=binarySearch( array, target );
     
    			if (index >= 0)
    				System.out.printf("%d FOUND in array at index position %d\n",target,index );
    			else
    				System.out.printf("%d NOT found in array\n",target );
    		} while (true);
     
    	} // END MAIN
     
     
    	private static void printArray( int array[] )
    	{
    		System.out.printf("\nArray has %d values:\n",array.length );
    		for( int i=0 ; i<array.length ;++i )
    			System.out.print(array[i] + " " );
    		System.out.println("\n");
    	}
     
    	// puts the new value into the array at its proper sorted position by shuffline higher values up one place
    	//	and opening up a hole where the new val goes. All values are kept contiguous from the front
     
    	private static void insertInOrder( int array[], int count, int newVal )
    	{
    		int i;
    		for (i=count-1; i>=0 && newVal<array[i] ; --i)
    			array[i+1] = array[i];
     
    		array[i+1] = newVal;
    	}
     
    	// if target not found returns -1
    	// else returns index position where target found
     
    	public static int binarySearch( int array[], int target )
    	{
    	int low=0;
    	int high=array.length;
    	int spot=(low+high)/2;
    	int i=0;
     
    	while (i==0)
    	{
    	if (array[spot]<target)
    	{
    	low=spot+1;
    	break;
    	}
     
    	else if(array[spot]>target)
    	{
    	high=spot-1;
    	break;
    	}
     
    	else if (array[spot]==target)
    	return spot;
     
    	}
    	return NOT_FOUND;
     
    	}
     
    } //END class


  2. #2
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,424
    My Mood
    Hungover
    Thanks
    144
    Thanked 636 Times in 540 Posts

    Default Re: Binary Search for an array of random ints - Can't find the target value

    What exactly do you mean "when in comes time to pick a target value and search for it"? Are you having trouble with the actual search, or reading in a value, or something else?
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  3. #3
    Junior Member
    Join Date
    Jan 2012
    Posts
    6
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Binary Search for an array of random ints - Can't find the target value

    I mean that the user picks a value to search for in the array. My problem is in the search method

  4. #4
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,424
    My Mood
    Hungover
    Thanks
    144
    Thanked 636 Times in 540 Posts

    Default Re: Binary Search for an array of random ints - Can't find the target value

    Well, what have you done to debug it? Have you stepped through it with a debugger, or at least added some print statements to figure out what's going on? When does the flow of the program differ from what you expect?

    Recommended reading: http://www.javaprogrammingforums.com...t-println.html
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

Similar Threads

  1. How to find the larget number on binary search tree
    By Jurgen in forum What's Wrong With My Code?
    Replies: 4
    Last Post: December 24th, 2011, 11:26 AM
  2. Using Comparable in Binary Search
    By Shaybay92 in forum Algorithms & Recursion
    Replies: 3
    Last Post: November 12th, 2011, 03:23 AM
  3. Binary Search Help
    By OwsumEmam in forum What's Wrong With My Code?
    Replies: 7
    Last Post: March 31st, 2011, 11:01 PM
  4. Binary Search Help!
    By Allicat in forum What's Wrong With My Code?
    Replies: 8
    Last Post: March 15th, 2011, 04:03 PM
  5. Binary Search Tree
    By Koren3 in forum What's Wrong With My Code?
    Replies: 9
    Last Post: November 12th, 2009, 09:27 AM