What is a linear search?
A linear search checks each element in a list one by one from the start until the target is found or the list ends. It does not require the list to be sorted.
What is a binary search?
Binary search is an algorithm that finds a target value in a sorted array by repeatedly dividing the search interval in half. It compares the target to the middle element and eliminates half of the remaining elements each step.
What condition must be true for a binary search to work?
The array must be sorted in ascending order (or descending, depending on implementation) before binary search can be applied.
Describe the first step of a binary search on a sorted array.
Compare the target value to the middle element of the array. If they match, return the position. If not, decide which half to continue searching in based on whether the target is less or greater than the middle element.
In binary search, if the target is less than the middle element, which half is searched next?
The lower half (elements with indices less than the middle index) is searched next.
In binary search, if the target is greater than the middle element, which half is searched next?
The upper half (elements with indices greater than the middle index) is searched next.
What happens if the search interval becomes empty in binary search?
If the remaining half is empty, the target is not in the array, and the search terminates as unsuccessful.
What is the time complexity of binary search in the worst case?
Binary search runs in logarithmic time, O(log n), where n is the number of elements in the array.
How does the number of steps in binary search grow as the size of the sorted array doubles?
The number of steps increases by only 1 (since log2(2n) = log2(n) + 1). For example, searching 8 elements takes at most 3 steps, and 16 elements takes at most 4 steps.
How does the number of steps in linear search grow as the size of the list doubles?
The maximum number of steps doubles as well, because linear search may need to check every element. So if a list has n elements, worst-case steps are n.
Which search algorithm is faster for large sorted arrays: linear or binary?
Binary search is faster for large sorted arrays because it has O(log n) time complexity compared to linear search's O(n).
When might linear search be preferred over binary search?
Linear search is preferred for small arrays or when the data is unsorted, because binary search requires the array to be sorted first.
What is the main disadvantage of binary search compared to linear search?
The main disadvantage is that binary search requires the array to be sorted, which may add extra cost if the data changes frequently.
Define the term 'logarithmic time' in the context of binary search.
Logarithmic time means the number of operations grows proportionally to the logarithm of the input size. For binary search, the worst-case number of comparisons is O(log n).
What does the variable 'm' represent in the binary search algorithm?
'm' is the index of the middle element of the current search interval, calculated as L + floor((R - L) / 2).
In the binary search procedure, what are the initial values of L and R?
L is set to 0 (the first index) and R is set to n-1 (the last index), where n is the number of elements in the array.
What is the termination condition for an unsuccessful binary search?
The search terminates unsuccessfully when L > R, meaning the search interval is empty.
Give an example of a binary search on a sorted array of 5 elements: [2, 5, 8, 12, 16], searching for 12. Show the steps.
Step 1: L=0, R=4, m=2 (value 8). 8 < 12, so L=3. Step 2: L=3, R=4, m=3 (value 12). 12 == 12, return index 3.
What is the maximum number of comparisons needed to find an element in a sorted array of 1,000,000 elements using binary search?
At most about 20 comparisons, because log2(1,000,000) ≈ 19.93, so the worst case is 20 comparisons.
What does 'half-interval search' mean?
It is another name for binary search, because each step eliminates half of the remaining search interval.
What is the time complexity of linear search in the worst case?
Linear search has a worst-case time complexity of O(n), where n is the number of elements, because it may need to check every element.
Why is binary search not suitable for unsorted data?
Because binary search relies on the order of elements to decide which half to discard. If the data is unsorted, the middle element gives no reliable information about which half contains the target.
What is the key difference between linear and binary search in terms of data requirement?
Linear search works on any list, sorted or unsorted, while binary search requires the list to be sorted.
If you have a sorted array of 100 elements, what is the maximum number of steps binary search will take?
At most 7 steps, because log2(100) ≈ 6.64, so the worst case is 7 comparisons.