Question 1

Suppose we are using binary search on an array with approximately 1,000,000 elements. How many visits should we expect to make in the worst case?

Accepted Answer

Binary search has a time complexity of O(log n). For 1,000,000 elements, log2(1,000,000) is approximately 20, so in the worst case, we would expect to make about 20 visits.

Question 2

Given an ordered array with 15 elements, how many elements must be visited in the worst case of binary search?

Accepted Answer

The answer of Given an ordered array with 15 elements,...

Question 3

Which of the following statements about running times of algorithms is correct?

Accepted Answer

When determining the running time, constants are not taken into consideration because Big O notation focuses on the growth rate as input size increases, ignoring constant factors and lower-order terms.

Question 4

Another name for linear search is ____ search.

Accepted Answer

Linear search is also known as sequential search.

Question 5

Can you search the following array using binary search?
Int[] A = {6, 5, 4, 2, 0, 1, -1, -17};

Accepted Answer

Binary search requires the array to be sorted in either ascending or descending order. The given array is not sorted, so binary search cannot be applied.

Question 6

The partial linear search method below is designed to search an array of String objects. Select the expression that would be needed to complete the method. public static int search(String[] a, String item)
{
For (int i = 0; i < a.length; i++)
{
If ( ____________________________ )
{
Return i;
}
Return -1;
}
}

Accepted Answer

The `equals` method is used to compare the content of two String objects for equality.

Question 7

The partial binary search method below is designed to search an array of String objects sorted in ascending order. Select the expression that would be needed to complete the method. public static int search(String[] a, int low, int high, String item)
{
If (low <= high)
{
Int mid = (low + high) / 2;
Int result = ____________________________;
If (result == 0)
{
Return mid;
}
Else if (result < 0)
{
Return search(a, mid + 1, high, item);
}
Else
{
Return search(a, low, mid - 1, item);
}
}
Return -1;
}

Accepted Answer

The answer of The partial binary search method below is...

Question 8

Given an ordered array with 31 elements, how many elements must be visited in the worst case of binary search?

Accepted Answer

The answer of Given an ordered array with 31 elements,...

Question 9

The following code is an example of a ___ search. public static int search(int[] a, int v)
{
For (int i = 0; i < a.length; i++)
{
If (a[i] == v) { return i; }
}
Return -1;
}

Accepted Answer

The code iterates through each element of the array sequentially to find the target value, which is characteristic of a linear search.

Question 10

A portion of your program includes the loop shown in the code snippet below to examine the elements of an array arr:
Int count = 0;
Int targetVal = 70;
For (int i = 0; i < arr.length; i++)
{
If (arr[i] >= targetVal)
{
Count++;
}
}
What can you conclude about the running time of this section of code?

Accepted Answer

The loop iterates over the array of length n, and for each element, it performs a constant-time operation. Therefore, the running time of this section of code is O(n).

Question 11

The analysis for the number of visits in a binary search begins with the equation, T(n) = T(n / 2) + 1. What does the number 1 represent in this equation?

Accepted Answer

The number 1 represents the visit to the middle element of the array before deciding which half to recursively search.

Question 12

If an element is present in an array of length n, how many element visits, in the worst case, are necessary to find it using a linear search?

Accepted Answer

In a linear search, each element is checked one by one from the start to the end of the array. In the worst case, the element is found at the last position or not present at all, requiring n visits.

Question 13

A portion of your program implements a loop in which each step contains a fixed number of actions. What can you conclude about the running time of this section of code?

Accepted Answer

The running time of a loop with a fixed number of actions is O(n), where n is the number of iterations of the loop.

Question 14

If an element is present in an array of length n, how many element visits, on average, are necessary to find it using a linear search?

Accepted Answer

In a linear search, on average, you will need to check half of the elements to find the target, so the average number of visits is n/2.

Question 15

Suppose you have a phone number and need to find the address that it corresponds to. If there are 2,000,000 entries, how many do you expect to search in a printed phone directory before finding the address you are looking for?

Accepted Answer

In a printed phone directory, entries are typically sorted alphabetically or numerically. On average, you would expect to search through half of the entries before finding the one you are looking for, which is approximately 1,000,000 records in this case.

Question 16

Binary search is an ____ algorithm.

Accepted Answer

Binary search is an algorithm that divides the search interval in half each time, leading to a time complexity of O(log n).

Question 17

If you implement a recursive linear search, its performance will be ____.

Accepted Answer

A recursive linear search has a time complexity of O(n) because it checks each element in the list sequentially until it finds the target element or reaches the end of the list.

Question 18

The method findLargest examines the elements of an array arr which contains non-negative values public static int findLargest(int[] arr)
{
Int curLargest = -1;
For (int i = 0; i < arr.length; i++)
{
If (arr[i] >= curLargest)
{
CurLargest = arr[i];
}
}
Return curLargest;
}
What can you conclude about the running time of this section of code?

Accepted Answer

The running time of this code is O(n) because it iterates through the array once, and each iteration takes constant time.

Question 19

A search technique where, in each step, you split the size of the search in half is called a____ search.

Accepted Answer

Binary search is a search technique where, in each step, you split the size of the search in half.

Question 20

A binary search is generally ____ a linear search.

Accepted Answer

A binary search is faster than a linear search because it divides the search interval in half each time, resulting in a time complexity of O(log n), compared to the O(n) time complexity of a linear search.

Quiz 14: Sorting and Searching