Unit 10: Sorting and searching Flashcards
What is linear search?
A method of finding an element by checking each element sequentially until a match is found or the end is reached.
What is the maximum number of visits in a linear search for n elements?
n visits.
What is an advantage of linear search?
It does not require the array to be sorted.
What is the return value of linearSearch() if the element is not found?
-1.
What are the disadvantages of linear search?
Slow on large datasets
What is binary search?
Binary search repeatedly divides a sorted array in half to find the target value.
What condition must an array meet to use binary search?
The array must be sorted.
How does binary search compare to linear search for 1000 elements?
Linear search: ~500 visits; Binary search: ~10 visits.
What are the advantages of binary search?
Much faster than linear search on large datasets
What is the time complexity of binary search?
O(log₂ n).
What are the disadvantages of binary search?
Array must be sorted beforehand
What is Big O notation?
To describe how the runtime of an algorithm grows relative to the input size.
Why is Big O notation important?
- Helps predict performance on large inputs
- Useful for comparing algorithms
What does O(1) mean?
Constant time — the runtime does not change with input size. = accessing array elements
What does O(n) mean?
Linear time — the runtime grows proportionally with the input size.
What does O(n²) mean?
Quadratic time — runtime grows proportionally to the square of the input size. = Nested Loops
Why is sorting important before binary search?
Binary search requires a sorted array; otherwise, it won’t find the correct element.
What is Merge Sort?
Merge Sort is a divide-and-conquer algorithm. It splits the array into two halves, recursively sorts them, and then merges the sorted halves back together.
What is Selection Sort?
Selection Sort is a simple sorting algorithm that repeatedly selects the smallest (or largest) element from the unsorted part of the list and swaps it with the first unsorted element.
What is space complexity in algorithms?
Space complexity refers to the amount of memory an algorithm needs to run, relative to the size of the input. It includes both auxiliary space (extra space used) and total space (input data plus extra space). Examples:
O(1): Constant space. O(n): Space proportional to the input size.
How does Selection Sort work step-by-step?
- Find the smallest element in the unsorted part of the list.
- Swap it with the first unsorted element.
- Repeat the process for the remaining unsorted part until the list is sorted.
What is a major disadvantage of Selection Sort?
Selection Sort is inefficient for large lists because of its O(n²) time complexity, making it slower compared to more advanced algorithms like Quick Sort or Merge Sort.
What does this method do?
public static int linearSearch(int[] a, int value) {
for (int i = 0; i < a.length; i++) {
if (a[i] == value) return i;
}
return -1;
}
It performs a linear search and returns the index of the found value or -1 if not found.
