• (2 Pages)
• 1
• 2

## 23 Replies - 2237 Views - Last Post: 27 January 2013 - 09:28 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=309310&amp;s=2b3ab254aa4902706c979fb779973d41&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 k3y

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

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

### #2 andrewsw

• blow up my boots

Reputation: 6549
• Posts: 26,553
• Joined: 12-December 12

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

### #3 k3y

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

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

### #4 GregBrannon

• D.I.C Lover

Reputation: 2250
• Posts: 5,340
• Joined: 10-September 10

Posted 25 January 2013 - 01:59 PM

k3y, 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

### #5 k3y

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

Posted 25 January 2013 - 02:01 PM

GregBrannon, on 25 January 2013 - 03:59 PM, said:

k3y, 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

### #6 k3y

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

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

### #7 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12315
• Posts: 45,414
• Joined: 27-December 08

Posted 25 January 2013 - 02:58 PM

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

### #8 k3y

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

Posted 25 January 2013 - 03:06 PM

macosxnerd101, on 25 January 2013 - 04:58 PM, said:

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

I think so.

### #9 CasiOo

• D.I.C Lover

Reputation: 1577
• Posts: 3,551
• Joined: 05-April 11

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

### #10 k3y

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

Posted 25 January 2013 - 03:15 PM

CasiOo, 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

### #11 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12315
• Posts: 45,414
• Joined: 27-December 08

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.

### #12 CasiOo

• D.I.C Lover

Reputation: 1577
• Posts: 3,551
• Joined: 05-April 11

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

### #13 k3y

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

Posted 25 January 2013 - 03:27 PM

macosxnerd101, 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;
}
}

```

### #14 k3y

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

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;
}
}

```

### #15 GregBrannon

• D.I.C Lover

Reputation: 2250
• Posts: 5,340
• Joined: 10-September 10