Section 2(Search & Sorting)

What is Searching, and what are the two primary searching algorithms in C++?

Searching is locating the index of a target value within a collection. The two primary algorithms are: 1. Linear Search, 2. Binary Search.

How does Linear Search work, and on what types of arrays can it be used?

Sequentially checks every element one-by-one from index 0 until the target is found or the end is reached. Works on BOTH sorted and unsorted arrays. Best for small or unsorted datasets.

How does Binary Search work, and what is its strict prerequisite?

Prerequisite: The array MUST BE SORTED. Uses divide-and-conquer: examines the middle element. If equal, search ends. If target is smaller/larger, repeats on the left/right half. Halves search space each step (O(log n)).

What is Sorting, what are the two algorithms covered in the review slides, and what is their time complexity?

Sorting is arranging elements in ascending or descending order. Algorithms: Bubble Sort and Selection Sort. Both are comparison-based with quadratic time complexity O(n^2).

How does Bubble Sort work step-by-step?

Repeatedly steps through comparing adjacent elements (arr[j] and arr[j+1]). If out of order, they are swapped. The largest remaining element "bubbles up" to the end after each pass.

How does Selection Sort work step-by-step (ascending)?

Divides array into sorted (left) and unsorted (right) parts. In each pass, finds the smallest element in the unsorted part and swaps it into the correct position. Performs at most one swap per pass.

Trace the Linear Search implementation: int linearSearch(int arr[], int n, int x) { … } with arr[] = {10, 20, 30, 40}, target = 30. What is the output and meaning of -1?

Output: 2. \n Returning -1 is the standard sentinel indicating the target was not found in the array.

What will be the output of the following code snippet? \n int arr[] = {5, 3, 8, 6}; int n = sizeof(arr) / sizeof(arr[0]); int index = linearSearch(arr, n, 8); cout << index;

B) 2 (since target 8 is found at index position 2).

What will be the output of the following code snippet? \n int arr[] = {2, 4, 6, 8, 10}; int index = binarySearch(arr, 5, 7); cout << index;

C) -1 \n Explanation: Since 7 does not exist in the sorted array, binary search returns -1 (Not Found).

Trace Bubble Sort pass-by-pass on: [5, 3, 8, 4, 2]. Show the array after each pass.

Pass 1: [3, 5, 4, 2, 8] \n Pass 2: [3, 4, 2, 5, 8] \n Pass 3: [3, 2, 4, 5, 8] \n Pass 4: [2, 3, 4, 5, 8] (Final Output)

Trace Selection Sort pass-by-pass on: [29, 10, 14, 37, 13]. Show the array after each pass.

Pass 1: [10, 29, 14, 37, 13] \n Pass 2: [10, 13, 14, 37, 29] \n Pass 3: [10, 13, 14, 37, 29] \n Pass 4: [10, 13, 14, 29, 37] (Final Output)

What will be the final sorted array after Bubble Sort? \n int arr[] = {7, 2, 5, 1}; bubbleSort(arr, 4);

A) 1 2 5 7

After the SECOND pass of Selection Sort (ascending), what will be the array? \n int arr[] = {20, 15, 10, 5}; selectionSort(arr, 4);

A) 5 10 15 20 \n Trace: Pass 1 -> [5, 15, 10, 20]. Pass 2 -> [5, 10, 15, 20].

What is the ideal use case for Bubble Sort?

Small or nearly sorted datasets. When data is already mostly sorted, an optimized Bubble Sort can finish in a single pass (O(n) time).

Why does the inner loop condition in Bubble Sort use j < n - i - 1 instead of j < n - 1?

1. - 1 prevents out-of-bounds access on arr[j + 1]. \n 2. - i is an optimization because the i largest elements have already bubbled to the end and are in their permanent sorted positions.

What is the core mechanism of Selection Sort?

Maintains a sorted subarray (left) and an unsorted subarray (right). Scans the unsorted part, finds the absolute minimum element's index (minIdx), and swaps it with arr[i].

Trace the Slide 15 Linear Search example: Input Array: [3, 1, 4, 1, 5], Target: 4. Show comparisons and result.

Comparison 1: arr[0] = 3 (no match). \n Comparison 2: arr[1] = 1 (no match). \n Comparison 3: arr[2] = 4 (Match!). \n Returns: Index 2.

If list = [10, 20, 30] and search value = 99 in a linear search trace, what are found, position, and index when returning?

found: false, position: -1, index: 3. \n Return value: -1 (Not Found).

What are the three sections Binary Search divides the array into during a step?

1. The Middle Element (arr[mid]), \n 2. Left half (low to mid - 1), \n 3. Right half (mid + 1 to high).

Trace the Slide 18 Binary Search example: Input Array: [1, 2, 3, 4, 5], Target: 4. Show steps.

Step 1: low=0, high=4, mid=2 (arr[2]=3). Since 4 > 3, low = 3. \n Step 2: low=3, high=4, mid=3 (arr[3]=4). Match found! Returns: Index 3.