CIS 255 Searching and Efficiency

Question 1

The linear (sequential) search algorithm runs in ________time.

Question 2

What is the term used for binary search's run time?

Question 3

The binary search algorithm is __________ efficient than the linear search, but it requires that the array be _________.

Question 4

You can perform binary search on any dataset (Strings, numbers, sorted, unsorted, etc.). True or False.

Question 5

In all cases, with any given sorted dataset, binary search will always make fewer comparisons than linear search. True or False.

The following questions ask about tracing a linear search. The answers show the indices of the array that are visited for the search.

For linear search, use the "optimized" version that stops when the target is found.

Question 6

What indices will be visited for the data below?

[22, 14, 18, 21, 29, 17, 16, 15]
target = 17

Question 7

What indices will be visited for the data below?

[22, 14, 18, 21, 29, 17, 16, 15]
target = 88

Question 8

What indices will be visited for the data below?

[22, 14, 18, 21, 29, 17, 16, 15]
target = -55

The following questions ask about tracing a linear search on sorted data. The answers show the indices of the array that are visited for the search.

For this linear search, use the "optimized" version that stops when the target is found and the version that stops if it's no longer possible for a target to be in the array.

Question 9

What indices will be visited for the data below?

[14, 15, 18, 21, 24, 36, 38, 42]
target = 36

Question 10

What indices will be visited for the data below?

[14, 15, 18, 21, 24, 36, 38, 42]
target = 29

Question 11

What indices will be visited for the data below?

[14, 15, 18, 21, 24, 36, 38, 42]
target = -17

The following questions ask about tracing a binary search. Use the two binary search algorithm given in the Searches.java file included in the lecture code files or the one posted below.

To trace the binary search, list the value of first, last, and mid for each pass through the loop or method. See this page for examples.Links to an external site.

Note that submitting only the final answer or any other format of a trace will receive no credit.

public static int binarySearchIterative(int[] numbers, int target) {
int first = 0;
int last = numbers.length - 1;

while (first <= last) {
int mid = (first + last) / 2;

if (numbers[mid] == target) {
return mid;
} else if (numbers[mid] < target) {
first = mid + 1;
} else { // numbers[mid] > target
last = mid - 1;
}
}
return -1;
}

Question 12

Trace binary search on the dataset below. List first, last, and mid for each pass through the loop or each recursive method call.

[3, 5, 8, 9, 12, 14, 18, 19, 21, 23, 24, 26]
target = 23

Question 13

Trace binary search on the dataset below. List first, last, and mid for each pass through the loop or each recursive method call.

[3, 5, 8, 9, 12, 14, 18, 19, 21, 23, 24, 26]
target = 16

For the next set of questions, determine the order of growth (Big O) of the code or the situation.

Question 14

// myList is type ArrayList

for(int i=1; i < myList.size() / 2 ; i++) {
System.out.println(myList.get(i));
}

Question 15

// arrayList is type ArrayList filled with text of numbers that match their index: "0", "1", "2", "3", "4", ...

int n = arrayList.size();

for(int i=0; i < n; i++) {
String numberString = Integer.toString(i);
arrayList.remove(numberString);
}

Question 16

// arrayList is type ArrayList

for(int i=0; i < arrayList.size(); i++) {
System.out.println(arrayList.get(i));
}

Question 17

for(int i=0; i < n; i++) {
// code that is independent of n
}

for(j=0; j < n; j++) {
// code that is independent of n
}

Question 18

for(int i=0; i < 10; i++) {
for(int j=0; j < 100; j++) {
// code that is O(n)
}
}

Question 19

display all integers in an array of integers

Question 20

display a value at a specified index in an array of integers

For example, display the 3rd element in the array, display the 10th element in the array, etc.

Question 21

int sum=0;

for(int counter = n; counter > 0; counter = counter-2) {
sum = sum + counter;
}

Hint: pay careful attention to how the update function of the loop changes how often the loop runs! (What happens if you double the problem size, how does the number of loops change?)

Question 22

int sum=0;

for(int counter = 1; counter < n; counter = 2 * counter) {
sum = sum + counter;
}

Hint: pay careful attention to how the update function of the loop changes how often the loop runs! (What happens if you double the problem size, how does the number of loops change?)

Question 23

for(int i=1; i <= n; i++) {
for(int j=0; j < n; j++) {
for(int k=1; k < 10; k++) {
// code here that is independent of n
}
}
}

Question 24

for(int i=1; i <= n; i++) {
for(int j=0; j < n; j++) {
for(int k=1; k < n; k++) {
// code here that is independent of n
}
}
}

Question 25

for(int i=0; i < 100; i++) {
System.out.println(n);
}

Question 26

An algorithm that is O(1) _______.

Question 27

An O(n) algorithm is referred to as having a _______ run time.

Write a binary search method that uses recursion to find the index of a target object in an array.

The method header is:

public static int binarySearch(Comparable[] objects, Comparable target)

The target is some object whose class implements Comparable. The array holds Comparable objects and is sorted.

The method can be invoked with any object whose class implements Comparable (e.g., Strings, Integers, etc.).

Review the driver program for examples.

Hint: Include a helper method with additional parameters. If you do this, be sure to include both the helper method and the original method with the call to the helper in your answer.

Question 28

Paste your complete recursive binary search method here.

The method below creates a List of all duplicate integers found on a List. This code runs in O(n³) time. This is bad!

For this question, write a new method to accomplish the same task in O(n) time.

1. Before you begin to write your own code, carefully review the method below. Make sure you understand why that is the order of growth... it's not because of the three loops! If you aren't sure, post to the discussion board!

2. Write a new method to create a list of all duplicate integers found on a List.

• Note that you are not revising or fixing the method below.
• You are writing a new method.
• Your method should be linear O(n).

Details about your method:

• The numbers in the integer list passed in as a parameter are in the range -5n to 5n, where n is the size of the list.
  • Example: if the list is size 10, the numbers in the list are in the range -50 to 50.
  • Example: if the list is size 100, the numbers are in the range -500 to 500
• If a duplicate number shows up more than once on the original list, it should also show up more than once on the duplicate list.
  • Example: if the original list contains [1, 1, 1, 2, 2, 3, 4, 5, 5, 5], then the duplicates list should contain [1, 1, 2, 5, 5]
• The order of your duplicates list does not matter. For ease in testing/comparing, the driver program sorts the lists before printing.

Hints:

• Remember that you can often improve efficiency by using more space!
• Take advantage of the fact that you know something about the range of the numbers on the list!
• Carefully check the Big-O of any methods you use (e.g., sorting methods, contains methods, remove methods, etc.).
  • If any of those methods are worse than O(n), you should not use them!
  • We haven't covered sort (yet), but Collections.sort(...) is not linear!

Use the driver program to test your code.

public static List< Integer > findDuplicatesBad(List< Integer > numbers) {
List< Integer > duplicateList = new ArrayList< Integer >();
for(int i=0; i< numbers.size(); i++) {
int numberEvaluating = numbers.get(i);
boolean duplicateFound = false;

for(int j=i+1; j< numbers.size() && !duplicateFound; j++) {
int numberChecking = numbers.get(j);

if(numberEvaluating==numberChecking && !duplicateList.contains(numberEvaluating)) {
duplicateFound = true;

for(int k=j; k< numbers.size(); k++) {
if(numberChecking==Integer.valueOf(numbers.get(k))) {
duplicateList.add(numberChecking);
}
}
}
}
}
return duplicateList;
}

Question 29

Paste your complete linear method here.