2 BINARY SEARCH

Question 1

What is binary search?

Answer 1

An algorithm for efficiently searching a sorted list by repeatedly dividing the list in half.

Question 2

What does binary search discard during its process?

Answer 2

It discards the half of the list that does not contain the target value.

Question 3

True or False: Binary search can be applied to unsorted data.

Answer 3

False

Question 4

What is the primary advantage of binary search over linear scan?

Answer 4

Binary search is more efficient as it reduces the search space by half each iteration.

Question 5

Define linear scan.

Answer 5

An algorithm that searches for a target value by testing each value in a list one by one.

Question 6

What is the worst-case time complexity of linear scan?

Answer 6

O(N)

Question 7

In what scenario is linear scan guaranteed to find the target?

Answer 7

When the item is in the data.

Question 8

What is a key characteristic of binary search regarding data?

Answer 8

It works only on sorted data.

Question 9

What does IndexLow represent in binary search?

Answer 9

The lowest index of the current search space.

Question 10

What does IndexHigh represent in binary search?

Answer 10

The highest index of the current search space.

Question 11

How does binary search determine the midpoint?

Answer 11

IndexMid = Floor((IndexHigh + IndexLow) / 2)

Question 12

What happens if A[IndexMid] < target in binary search?

Answer 12

Adjust IndexLow to IndexMid + 1.

Question 13

What does binary search return if the target is not found?

Answer 13

-1

Question 14

What is the time complexity of binary search?

Answer 14

O(log N)

Question 15

What indicates the end of the search in binary search?

Answer 15

When IndexHigh < IndexLow.

Question 16

Fill in the blank: The binary search algorithm can be implemented using a single ______.

Answer 16

WHILE loop

Question 17

How can binary search be adapted for continuous data?

Answer 17

By using high and low bounds on the values themselves.

Question 18

What is the significance of binary search in computer science?

Answer 18

It illustrates the interaction between data structures and algorithms.

Question 19

True or False: Binary search guarantees both speed and correctness.

Answer 19

True

Question 20

What type of data structure does binary search utilize effectively?

Answer 20

Sorted arrays or lists.

Question 21

What is an example of a practical application of binary search?

Answer 21

Searching for a word in a dictionary.

Question 22

What do we mean by ‘absent values’ in the context of binary search?

Answer 22

Values that are not present in the list being searched.

Question 23

What is the primary concept of binary search?

Answer 23

Binary search is a method for finding a target value within a sorted array by repeatedly dividing the search interval in half.

Question 24

In the context of coffee brewing, what are the upper and lower bounds for the optimal amount of coffee grounds?

Answer 24

LowerBound = 0 tablespoons, UpperBound = 5 tablespoons.

Question 25

What is the purpose of defining a midpoint in a binary search?

Answer 25

To test whether the target value lies above or below the midpoint, thus refining the search bounds.

Question 26

What is the significance of the condition 'UpperBound – LowerBound < threshold' in binary search?

Answer 26

It determines when to terminate the search once the range is sufficiently small.

Question 27

True or False: A linear scan through options is more efficient than binary search.

Answer 27

False.

Question 28

What is a key advantage of binary search compared to a linear scan?

Answer 28

Binary search has a logarithmic runtime, significantly reducing the number of comparisons needed for large datasets.

Question 29

What is the worst-case runtime of a linear scan?

Answer 29

Linear with the size of the data, requiring N comparisons.

Question 30

What is the worst-case runtime of binary search?

Answer 30

Logarithmic with the size of the data set, proportional to log2 N.

Question 31

Fill in the blank: Bisection search finds the zero of a function by tracking bounds where the function is _______ and _______.

Answer 31

above zero, below zero.

Question 32

What is the relationship between problem structure and algorithm efficiency?

Answer 32

Designing algorithms by using the structure in the problems themselves helps create efficient solutions.

Question 33

What happens during a bisection search?

Answer 33

The interval is repeatedly divided in half at the midpoint to zoom in on the value of x where the function equals zero.

Question 34

How does binary search maintain better precision compared to a linear scan?

Answer 34

It narrows down the search range by halving it, allowing for more precise targeting of the optimal value.

Question 35

Why is binary search considered a fundamental concept in computer science?

Answer 35

It exemplifies how to efficiently utilize data structure properties to enhance algorithm performance.

Question 36

What is the main drawback of using a linear scan for searching?

Answer 36

It can be time-consuming due to the need to check every single value.

Question 37

True or False: Binary search requires a sorted array to function.

Answer 37

True.

Question 38

What is an example of a practical application of binary search beyond finding values in an array?

Answer 38

Determining optimal quantities, such as the ideal amount of coffee grounds.

Question 39

What is the significance of the term 'threshold' in binary search?

Answer 39

It defines how small the range must be to conclude the search.

Question 40

How does binary search differ in approach compared to linear search?

Answer 40

Binary search divides the search space in half at each step, while linear search examines each possible value sequentially.