Binary VS Linear Search problem. [please help]

  • (2 Pages)
  • +
  • 1
  • 2

23 Replies - 1119 Views - Last Post: 27 January 2013 - 09:28 AM Rate Topic: -----

#1 k3y  Icon User is offline

  • D.I.C Head

Reputation: 36
  • View blog
  • Posts: 205
  • Joined: 25-February 12

Binary VS Linear Search problem. [please help]

Posted 25 January 2013 - 01:43 PM

Howdy folks;
I have been assigned a problem by my professor, and I think I have completed all of the points specified, however; he still says that I have not completed the assignment. I would deeply appreciate any help that anyone can provide. I have posted both my code, and the assignment below.
ASSIGNMENT

Quote

In this program you will prove that on average, binary search works better than linear search.
1. Create a sorted list of 20 numbers.
2. Search for each element using linear search and print out the number of iterations before the item is found.
3. Now use binary search and print the same information.
4. Print the average number of iterations for each search.
5. You should be able to show that binary search does not always perform better than linear search but does perform better on average.
You will find the Binary Search and the Sequential search in the Unit 10 Coding folder.

CODE:
import java.util.*;
public class Assignment1
{
	static Scanner console = new Scanner(System.in);
	public static void main(String[] args)
	{
		//point 1
		int[] numberList = {
			1, 2, 3, 4, 5,
			6, 7, 8, 9, 10,
			11, 12, 13, 14, 15,
			16, 17, 18, 19, 20
			};
			
		System.out.println("Please enter a number from 1 to 20 to search for");
		
		int userInput = 0;
		
		try
		{
		userInput = console.nextInt();
		} 
		catch(InputMismatchException e)
		{
			System.out.println("You must enter an integer");
		}
		
		if ((userInput <= 20) && (userInput >=1))
		{
			seqSearch(numberList, userInput);
			binSearch(numberList, userInput);
		}
	}
	public static void seqSearch(int[] anArray, int userInput)
	{
	int iterations = 0;
	int sum = 0;
	try
	{
		for(int x = 0; x < anArray.length; x++)
		{
			iterations++;
			if(anArray[x] == userInput)
			{
				
				System.out.println("target found(linear)");
				break;
			}
			sum += iterations;
		}
		//point 2
		System.out.println("total number of iterations(linear): " + iterations);
		System.out.println();
	}
	catch(ArrayIndexOutOfBoundsException e)
		{
		System.out.println("Something went wrong");
		}
	}
	public static void binSearch(int[] anArray, int userInput)
	{
		int iterations = 0;
		int start = 0;
		int end = anArray.length - 1;
		int mid;
		int sum;
	try{
		while (start <= end)
		{
			iterations++;
			mid = ((start + end) / 2);
			if (userInput == anArray[mid])
			{
				System.out.println("target found(binary)");
				break;
			}
			else if (userInput < anArray[mid])
			{
				end = mid-1;
			}
			else
			{
				start = mid + 1;
			}
		/*System.out.println("i" + iterations);
		System.out.println("s" + start);
		System.out.println("e" + end);
		System.out.println("m" + mid);*/
		}
		// point 3
		System.out.println("total number of iterations(binary): " + iterations);
		System.out.println();
		}
		catch(ArrayIndexOutOfBoundsException e)
		{
			System.out.println("Something went wrong");
		}
	}
}



Is This A Good Question/Topic? 0
  • +

Replies To: Binary VS Linear Search problem. [please help]

#2 andrewsw  Icon User is online

  • Fire giant boob nipple gun!
  • member icon

Reputation: 3184
  • View blog
  • Posts: 10,667
  • Joined: 12-December 12

Re: Binary VS Linear Search problem. [please help]

Posted 25 January 2013 - 01:51 PM

Quote

Search for each element


You are only searching for a single number, entered by the user. You need to create loops that will search for each of the 20 elements, using both a linear and binary search.

Actually, you have only completed part 1, so I'm surprised by your question.

This post has been edited by andrewsw: 25 January 2013 - 01:52 PM

Was This Post Helpful? 0
  • +
  • -

#3 k3y  Icon User is offline

  • D.I.C Head

Reputation: 36
  • View blog
  • Posts: 205
  • Joined: 25-February 12

Re: Binary VS Linear Search problem. [please help]

Posted 25 January 2013 - 01:53 PM

How the heck do I go about doing that? I thought binary and linear were just ways to search for things.

This post has been edited by k3y: 25 January 2013 - 01:59 PM

Was This Post Helpful? 0
  • +
  • -

#4 GregBrannon  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2197
  • View blog
  • Posts: 5,224
  • Joined: 10-September 10

Re: Binary VS Linear Search problem. [please help]

Posted 25 January 2013 - 01:59 PM

View Postk3y, on 25 January 2013 - 03:53 PM, said:

How the heck do I go about doing that?

C'mon, you know how. It's a simple loop from 1 through 20, inclusive. Each time through the loop, do a linear search and a binary search. You didn't even try to do number 4
Was This Post Helpful? 1
  • +
  • -

#5 k3y  Icon User is offline

  • D.I.C Head

Reputation: 36
  • View blog
  • Posts: 205
  • Joined: 25-February 12

Re: Binary VS Linear Search problem. [please help]

Posted 25 January 2013 - 02:01 PM

View PostGregBrannon, on 25 January 2013 - 03:59 PM, said:

View Postk3y, on 25 January 2013 - 03:53 PM, said:

How the heck do I go about doing that?

C'mon, you know how. It's a simple loop from 1 through 20, inclusive. Each time through the loop, do a linear search and a binary search. You didn't even try to do number 4

for(int x = 0; x < array.length; x++)
{
	linSearch(array[x]);
	binSearch(array[x]);
}


Something like that? I honestly have no idea.

This post has been edited by k3y: 25 January 2013 - 02:08 PM

Was This Post Helpful? 0
  • +
  • -

#6 k3y  Icon User is offline

  • D.I.C Head

Reputation: 36
  • View blog
  • Posts: 205
  • Joined: 25-February 12

Re: Binary VS Linear Search problem. [please help]

Posted 25 January 2013 - 02:21 PM

Am I getting any closer?
import java.util.*;
public class Assignment1
{
	static Scanner console = new Scanner(System.in);
	public static void main(String[] args)
	{
		//point 1
		int[] numberList = {
			1, 2, 3, 4, 5,
			6, 7, 8, 9, 10,
			11, 12, 13, 14, 15,
			16, 17, 18, 19, 20
			};
		
		for(int x = 0; x < numberList.length; x++)
		{
			System.out.println("sequential search: " + x);
			System.out.println(seqSearch(numberList, numberList[x]));
			System.out.println();
			System.out.println("binary search: " + x);
			System.out.println(binSearch(numberList, numberList[x]));
		}
	}
	public static int seqSearch(int[] array, int searchItem)
	{
		int iterations = 0;
		for(int x = 0; x < array.length; x++)
		{
			iterations++;
			if(array[x] == searchItem)
			{
				return x;
			}
		}
		return -1;
	}
	public static int binSearch(int[] array, int searchItem)
	{
		int iterations = 0;
		int start = 0;
		int mid;
		int end = array.length-1;
		while (start <= end)
		{
			iterations++;
			mid = ((start + end) / 2);
			if (searchItem == array[mid])
			{	
				return mid;
			}
			else if (searchItem < array[mid])
			{
				end = mid - 1;
			}
			else
			{
				start = mid + 1;
			}
		}
		return -1;
	}
}
			


This post has been edited by k3y: 25 January 2013 - 02:29 PM

Was This Post Helpful? 0
  • +
  • -

#7 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10364
  • View blog
  • Posts: 38,392
  • Joined: 27-December 08

Re: Binary VS Linear Search problem. [please help]

Posted 25 January 2013 - 02:58 PM

Run your code and test it. Does it work as expected?
Was This Post Helpful? 0
  • +
  • -

#8 k3y  Icon User is offline

  • D.I.C Head

Reputation: 36
  • View blog
  • Posts: 205
  • Joined: 25-February 12

Re: Binary VS Linear Search problem. [please help]

Posted 25 January 2013 - 03:06 PM

View Postmacosxnerd101, on 25 January 2013 - 04:58 PM, said:

Run your code and test it. Does it work as expected?

I think so.
Was This Post Helpful? 0
  • +
  • -

#9 CasiOo  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1372
  • View blog
  • Posts: 3,022
  • Joined: 05-April 11

Re: Binary VS Linear Search problem. [please help]

Posted 25 January 2013 - 03:06 PM

It does not print the average
The assignment said you should also print the average

This post has been edited by CasiOo: 25 January 2013 - 03:07 PM

Was This Post Helpful? 0
  • +
  • -

#10 k3y  Icon User is offline

  • D.I.C Head

Reputation: 36
  • View blog
  • Posts: 205
  • Joined: 25-February 12

Re: Binary VS Linear Search problem. [please help]

Posted 25 January 2013 - 03:15 PM

View PostCasiOo, on 25 January 2013 - 05:06 PM, said:

It does not print the average
The assignment said you should also print the average

I have just updated code. However, I am unsure of how to calculate the average. I think the code for the most part covers the points listed, no? Really wouldn't mind some help here. I thought I was doing it right D=
import java.util.*;
public class Assignment1
{
	static Scanner console = new Scanner(System.in);
	public static void main(String[] args)
	{
		//point 1
		int[] numberList = {
			1, 2, 3, 4, 5,
			6, 7, 8, 9, 10,
			11, 12, 13, 14, 15,
			16, 17, 18, 19, 20
			};
		
		//point 2
		for(int x = 0; x < numberList.length; x++)
		{
			System.out.println("sequential search: ");
			System.out.println(seqSearch(numberList, numberList[x]));
			System.out.println();
			System.out.println("binary search: ");
			System.out.println(binSearch(numberList, numberList[x]));
		}
	}
	
	public static int seqSearch(int[] array, int searchItem)
	{
		int iterations = 0;
		for(int x = 0; x < array.length; x++)
		{
			iterations++;
			if(array[x] == searchItem)
			{
				//point 2
				System.out.println("number of iterations(seq): " + iterations);
				return x;
			}
		}
		return -1;
	}
	
	public static int binSearch(int[] array, int searchItem)
	{
		int iterations = 0;
		int start = 0;
		int mid;
		int end = array.length-1;
		while (start <= end)
		{
			iterations++;
			mid = ((start + end) / 2);
			if (searchItem == array[mid])
			{
				//point 3
				System.out.println("number of iterations(bin): " + iterations);
				return mid;
			}
			else if (searchItem < array[mid])
			{
				end = mid - 1;
			}
			else
			{
				start = mid + 1;
			}
			int average = (itera
		}
		return -1;
	}
}


This post has been edited by k3y: 25 January 2013 - 03:18 PM

Was This Post Helpful? 0
  • +
  • -

#11 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10364
  • View blog
  • Posts: 38,392
  • Joined: 27-December 08

Re: Binary VS Linear Search problem. [please help]

Posted 25 January 2013 - 03:19 PM

Quote

However, I am unsure of how to calculate the average.

You add up the number of iterations and divide by the number of times you searched. This is covered in math classes since grade school...

Perhaps a counter variable to track iterations would be helpful.
Was This Post Helpful? 1
  • +
  • -

#12 CasiOo  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1372
  • View blog
  • Posts: 3,022
  • Joined: 05-April 11

Re: Binary VS Linear Search problem. [please help]

Posted 25 January 2013 - 03:19 PM

I would have changed the seq. and binary search methods into returning the number of used iterations instead
This should of course not be the case when outside of a school assignment where you are actually gonna use them to something useful :) But it will be a help when calculating the average and print iterations used
Was This Post Helpful? 2
  • +
  • -

#13 k3y  Icon User is offline

  • D.I.C Head

Reputation: 36
  • View blog
  • Posts: 205
  • Joined: 25-February 12

Re: Binary VS Linear Search problem. [please help]

Posted 25 January 2013 - 03:27 PM

View Postmacosxnerd101, on 25 January 2013 - 05:19 PM, said:

Quote

However, I am unsure of how to calculate the average.

You add up the number of iterations and divide by the number of times you searched. This is covered in math classes since grade school...

Perhaps a counter variable to track iterations would be helpful.

like this?
import java.util.*;
public class Assignment1
{
	static Scanner console = new Scanner(System.in);
	public static void main(String[] args)
	{
		//point 1
		int[] numberList = {
			1, 2, 3, 4, 5,
			6, 7, 8, 9, 10,
			11, 12, 13, 14, 15,
			16, 17, 18, 19, 20
			};
		
		//point 2
		for(int x = 0; x < numberList.length; x++)
		{
			System.out.println("sequential search: ");
			System.out.println(seqSearch(numberList, numberList[x]));
			System.out.println();
			System.out.println("binary search: ");
			System.out.println(binSearch(numberList, numberList[x]));
		}
	}
	
	public static int seqSearch(int[] array, int searchItem)
	{
		int iterations = 0;
		int average;
		for(int x = 0; x < array.length; x++)
		{
			iterations++;
			if(array[x] == searchItem)
			{
				//point 2
				System.out.println("number of iterations(seq): " + iterations);
			}
		}
		average = (iterations / array.length);
		return -1;
	}
	
	public static int binSearch(int[] array, int searchItem)
	{
		int iterations = 0;
		int start = 0;
		int mid;
		int end = array.length-1;
		int average;
		while (start <= end)
		{
			iterations++;
			mid = ((start + end) / 2);
			if (searchItem == array[mid])
			{
				//point 3
				System.out.println("number of iterations(bin): " + iterations);
				return mid;
			}
			else if (searchItem < array[mid])
			{
				end = mid - 1;
			}
			else
			{
				start = mid + 1;
			}
			average = (iterations/array.length);
			return average;
		}
		return -1;
	}
}


Was This Post Helpful? 0
  • +
  • -

#14 k3y  Icon User is offline

  • D.I.C Head

Reputation: 36
  • View blog
  • Posts: 205
  • Joined: 25-February 12

Re: Binary VS Linear Search problem. [please help]

Posted 26 January 2013 - 11:53 AM

Thank you everyone that helped me. Here is what I conjured up.
import java.util.*;
public class Assignment1
{
 static double binaryIterations = 0;
 static double linearIterations = 0;
 static int x = 0;
 static Scanner console = new Scanner(System.in);
 public static void main(String[] args)
 {
  //point 1 ~ sorted list
  int[] numberList = {
   1, 2, 3, 4, 5,
   6, 7, 8, 9, 10,
   11, 12, 13, 14, 15,
   16, 17, 18, 19, 20
   };
  
  //point 2a. loop to search for each element
  for(x = 0; x < numberList.length; x++)
  {
   seqSearch(numberList, numberList[x]);
   binSearch(numberList, numberList[x]);
  }
  System.out.println();
  System.out.println('\t' + "---------------------------------");
  System.out.println('\t' + "AVERAGE NUMBER OF ITERATIONS");
  System.out.println('\t' + "---------------------------------");
  //point 4. Print the average number of iterations for each search
  System.out.println('\t' + "Average linear search iterations " + (linearIterations/numberList.length));
  System.out.println('\t' + "Average binary serach iterations " + (binaryIterations/numberList.length));
 }
 
 public static int seqSearch(int[] array, int searchItem)
 {
  for(x = 0; x < array.length; x++)
  {
   linearIterations++;
   if(array[x] == searchItem)
   {
    //point 2b. print out number of iterations before item is found(linear)
    System.out.println("(linear)number of iterations to find " + array[x] + " = " + linearIterations);
    return x + 1;
   }
  }
  return -1;
 }
 public static int binSearch(int[] array, int searchItem)
 {
  int start = 0;
  int mid;
  int end = array.length-1;
  while (start <= end)
  {
   binaryIterations++;
   mid = ((start + end) / 2);
   if (searchItem == array[mid])
   {
    //point 3. print out number of iterations before item is found(binary)
    System.out.println("(binary)number of iterations to find " + array[x] + " = " + binaryIterations);
    System.out.println();
    return mid;
   }
   else if (searchItem < array[mid])
   {
    end = mid - 1;
   }
   else
   {
    start = mid + 1;
   }
  }
  return -1;
 }
}


Was This Post Helpful? 0
  • +
  • -

#15 GregBrannon  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2197
  • View blog
  • Posts: 5,224
  • Joined: 10-September 10

Re: Binary VS Linear Search problem. [please help]

Posted 26 January 2013 - 12:05 PM

Your averages are correct, but the number of iterations you report along the way are not. Your iteration counts are cumulative rather than specific to locating each number. You're doing the same for the binary search iteration counts.

Not sure if it's a big deal, but the way you're reporting the iteration counts is inaccurate.
Was This Post Helpful? 1
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2