Searching and Sorting

Question 1

What is a search algorithm?

Answer 1

A search algorithm is a method used to find the position of a specific value within a data structure such as an array or list.

Question 2

What is binary search?

Answer 2

Binary search is a search algorithm that repeatedly divides a sorted list in half to locate a target value.

Question 3

What condition must be true before binary search can be used?

Answer 3

The data must be sorted.

Question 4

What are the steps of binary search?

Answer 4

Find the middle element; compare with the target; if equal stop; if smaller search left half; if larger search right half; repeat until found or list empty.

Question 5

Why is binary search efficient?

Answer 5

Each comparison halves the search space, reducing the number of comparisons needed.

Question 6

What is the best case time complexity of binary search?

Answer 6

O(1) when the item is found immediately.

Question 7

What is the average time complexity of binary search?

Answer 7

O(log n) because the search space is halved each step.

Question 8

What is the worst case time complexity of binary search?

Answer 8

O(log n) when the element is at the deepest level or not found.

Question 9

What is the main disadvantage of binary search?

Answer 9

The data must be sorted before searching.

Question 10

What is a hash table?

Answer 10

A data structure that stores data using a hash function to determine the index where the data is stored.

Question 11

What is a hash function?

Answer 11

A function that converts a key into an index in a hash table, for example index = key mod table_size.

Question 12

What is a key in a hash table?

Answer 12

The value used by the hash function to determine where data should be stored.

Question 13

What is a hash collision?

Answer 13

When two different keys produce the same index in a hash table.

Question 14

Why do collisions occur?

Answer 14

Because the number of possible keys is larger than the number of positions in the hash table.

Question 15

What is chaining?

Answer 15

A collision resolution method where multiple values are stored at the same index using a list or linked list.

Question 16

What is linear probing?

Answer 16

A collision resolution method where the algorithm searches the next available space in the table sequentially.

Question 17

What is double hashing?

Answer 17

A collision resolution method where a second hash function is used to calculate a new index.

Question 18

What is the average time complexity of searching in a hash table?

Answer 18

O(1) because the hash function directly calculates the storage index.

Question 19

What is the worst case time complexity of a hash table search?

Answer 19

O(n) when many collisions occur.

Question 20

Compare binary search and hash table searching.

Answer 20

Binary search requires sorted data and has O(log n) time complexity; hash tables do not require sorted data and have average O(1) time complexity.