Revise later
SpaceTo flip
If confident
All Flashcards
What is Binary Search?
A search algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half.
What is Merge Sort?
A divide-and-conquer sorting algorithm that divides the input array into smaller sub-arrays, recursively sorts them, and then merges the sorted sub-arrays.
What is Recursion?
A programming technique where a function calls itself in order to solve a problem.
What is a Base Case?
The condition that stops a recursive function from calling itself infinitely.
What is Linear Search?
A searching algorithm that sequentially checks each element of a list until a match is found or the entire list has been searched.
What is Insertion Sort?
A sorting algorithm that builds the final sorted array one item at a time by repeatedly inserting the next element into its correct position within the already sorted portion of the array.
What is Selection Sort?
A sorting algorithm that repeatedly finds the minimum element from the unsorted portion of the array and places it at the beginning.
What is an ArrayList?
A resizable array implementation of the List interface in Java.
What is an Index?
The position of an element within an array or ArrayList, starting from 0.
What is a Sublist?
A contiguous portion of a list or array.
Why must a list be sorted for Binary Search?
Binary search works by repeatedly dividing the search interval in half. This requires knowing whether the target value is in the lower or upper half, which is only possible if the list is sorted.
What is the core idea behind Merge Sort?
Divide the list into smaller sublists, recursively sort the sublists, and then merge them back together in sorted order.
What is the time complexity of Linear Search?
O(n) in the worst case, where n is the number of elements in the list.
What is the time complexity of Binary Search?
O(log n), where n is the number of elements in the list.
What is the time complexity of Insertion Sort?
O(n^2) in the worst and average cases, where n is the number of elements in the list.
What is the time complexity of Selection Sort?
O(n^2) in all cases, where n is the number of elements in the list.
What is the time complexity of Merge Sort?
O(n log n) in all cases, where n is the number of elements in the list.
What is the space complexity tradeoff of Merge Sort?
Merge Sort requires more memory due to the creation of temporary arrays during the merge process.
What is the benefit of using recursion?
Recursion can make code more concise and easier to read for certain problems.
What is a potential drawback of using recursion?
Recursion can lead to stack overflow errors if the base case is not reached or the recursion depth is too large.
What does the following code output?
```java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
Collections.sort(arr);
System.out.println(arr);
```
[1, 2, 5, 8, 9]
Identify the error in the following code:
```java
public static int recursiveBinarySearch(ArrayList<Integer> array, int n, int left, int right) {
int middle = (left + right) / 2;
if (left > right) { return -1; }
else if (n == array.get(middle)) { return middle; }
else if (n < array.get(middle)) { recursiveBinarySearch(array, n, left, middle - 1); }
else if (n > array.get(middle)) { recursiveBinarySearch(array, n, middle + 1, right); }
}
```
The recursive calls don't return a value. Should be `return recursiveBinarySearch(...)`.
What does the following code output?
```java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
recursiveInsertionSort(arr, 0);
System.out.println(arr);
``` Assuming `recursiveInsertionSort` is correctly implemented.
[1, 2, 5, 8, 9]
What does the following code output?
```java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
recursiveSelectionSort(arr, 0);
System.out.println(arr);
``` Assuming `recursiveSelectionSort` is correctly implemented.
[1, 2, 5, 8, 9]
What does the following code output?
```java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
mergeSort(arr);
System.out.println(arr);
``` Assuming `mergeSort` is correctly implemented.
[1, 2, 5, 8, 9]
What does the following code output?
```java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
int index = recursiveLinearSearch(arr, 8, 0);
System.out.println(index);
```
2
What does the following code output?
```java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(1, 2, 5, 8, 9));
int index = recursiveBinarySearch(arr, 5, 0, arr.size() - 1);
System.out.println(index);
```
2
Identify the error in the following code:
```java
public static int recursiveLinearSearch(ArrayList<Integer> array, int n, int startingIndex) {
if (array.get(startingIndex) == n) { return startingIndex; }
else if (startingIndex == array.size() - 1) { return -1; }
else { recursiveLinearSearch(array, n, startingIndex); }
}
```
The recursive call does not increment `startingIndex`, leading to infinite recursion. Should be `recursiveLinearSearch(array, n, startingIndex + 1)`.
What does the following code output?
```java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
int index = recursiveLinearSearch(arr, 10, 0);
System.out.println(index);
```
-1
What does the following code output?
```java
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(1, 2, 5, 8, 9));
int index = recursiveBinarySearch(arr, 10, 0, arr.size() - 1);
System.out.println(index);
```
-1