Searching algorithms：練習問題

A linear search is performed on an array of 1,000 elements to find a value that is not present in the data. How many comparisons will the algorithm perform?

An array contains 2,048 sorted integers. In the worst-case scenario, how many comparisons will a binary search algorithm perform to determine if a value is in the array?

A programmer is choosing between a Binary Search and a Binary Tree Search for a system where the data is frequently updated with new items. What is a key disadvantage of the Binary Tree Search compared to the standard Binary Search in this specific context?

A programmer is searching for a value in a sorted array using the binary search algorithm. If the array contains 1,000,000 elements, what is the maximum number of comparisons required to find the target or determine it is not present?

A binary search tree (BST) contains \(n\) nodes. In the worst-case scenario, what is the time complexity of searching for a specific key if the tree is not balanced?

An algorithm is designed to find the shortest path between two points on a map represented as an unweighted graph. Identify which graph-traversal algorithm is most appropriate and state its Big-O time complexity if the graph has \(V\) vertices and \(E\) edges.

A programmer needs to locate a specific integer in a sorted array containing 1,024 elements. Explain why a binary search is significantly more efficient than a linear search in the worst-case scenario for this dataset.

A binary search tree (BST) is used to store \(n\) elements. Explain the conditions under which the search time complexity would degrade from \(O(\log n)\) to \(O(n)\).

Consider the following list of sorted names: [Alice, Bob, Charlie, David, Edward, Fiona, George].

(a) Trace the steps of a binary search to find the name 'Fiona'. Identify the middle element chosen at each step.
(b) What is the maximum number of comparisons needed for a binary search on a list of 128 elements?

Evaluate the efficiency of searching in a Binary Search Tree (BST) compared to a Binary Search on a sorted array.

(a) Under what condition does the time complexity of a BST search degrade from \(O(\log n)\) to \(O(n)\)?
(b) Describe how tree-traversal can be used to re-balance a tree to maintain \(O(\log n)\) performance.