IC217 Data Structures: Abstraction, Sorting, and Searching Algorithms

IC217 Data Structures Curriculum Overview

• IC217 Data Structures serves as a comprehensive foundational framework for computing, covering essential topics in problem-solving and software design.

• Lesson 1 introduces core computer science concepts including abstraction, data organization via sorting, and element retrieval via searching algorithms in Java.

• The lesson is structured around four fundamental topics:

  • Topic 01: Problem Solving Process

  • Topic 02: Abstraction

  • Topic 03: Sorting Algorithms

  • Topic 04: Searching Algorithms

Problem-Solving Process and Abstraction

• Abstraction is a central technique in computer science that decouples high-level logical operational concepts from low-level implementation details.

• The problem-solving framework requires a structured sequence of algorithmic development before lower-level code implementation begins.

• Abstraction enables programmers to establish defined computational interfaces without burdening client programs with internal algorithmic complexities.

• Practical software development relies on abstraction to build modular, maintainable, and scalable systems.

Overview of Sorting Algorithms

• Sorting is the process of arranging a collection of data items into a specified ordered sequence (e.g., numerical ascending or descending order).

• Sorting data structures is a fundamental precursor to enabling efficient search algorithms and data processing operations.

• Primary elementary sorting algorithms covered within the curriculum include:

  • Bubble Sort: A simple comparison-based algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

  • Insertion Sort: An algorithm that builds a final sorted array one item at a time by repeatedly taking elements from the unsorted segment and inserting them into their correct position.

  • Selection Sort: An algorithm that divides the input array into a sorted and an unsorted region, repeatedly selecting the minimum element from the unsorted region and moving it to the sorted region.

Searching Algorithms: Linear Search

• Linear Search (also known as Sequential Search) is a fundamental search algorithm used across linear collections of data items.

• The technique relies on sequentially traversing a data structure from start to end, inspecting each element encountered along the traversal path.

• Detailed execution mechanism:

  • The algorithm begins at index $0$ (the first element of the array).

  • Sequential checks are made over every item in the data structure, one element at a time.

  • For each element $x$, the algorithm tests whether $x == k$, where $k$ is the target search key.

  • If a match is identified ($x == k$), the search immediately terminates and returns the array index where the target key resides.

  • If $x \neq k$, the search continues sequentially to the subsequent element.

  • If the end of the collection is reached without finding a match, the algorithm terminates and returns $-1$ to indicate that the target item is absent.

• Linear search operates effectively on both unsorted and sorted data structures.

Linear Search Examples and Step-by-Step Traces

• Example 1: Searching for key $k = 1$ in the array [2, 4, 0, 1, 9]:

  • Target key set to $k = 1$

  • Index 0: Element value is 2. Comparison: $1 \neq 2$. Advance to next index.

  • Index 1: Element value is 4. Comparison: $1 \neq 4$. Advance to next index.

  • Index 2: Element value is 0. Comparison: $1 \neq 0$. Advance to next index.

  • Index 3: Element value is 1. Comparison: $1 == 1$. Match found! Return index 3.

• Example 2: Searching for target key 2 in a 6-element array [5, 9, 10, 2, 90, 4]:

  • Index 0: Element 5 checked. Comparison $5 \neq 2$.

  • Index 1: Element 9 checked. Comparison $9 \neq 2$.

  • Index 2: Element 10 checked. Comparison $10 \neq 2$.

  • Index 3: Element 2 checked. Comparison $2 == 2$. Element 2 found at index 3.

Java Implementation of Linear Search

• The complete Java source implementation for Linear Search (LinearSearch1) is structured as follows:

public class LinearSearch1 {
    public static int linearSearch(int[] inputArray, int key) {
        for (int i = 0; i < inputArray.length; i++) {
            if (inputArray[i] == key) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String args[]) {
        int[] arr1 = {5, 9, 10, 2, 90, 4};
        int key = 2;
        int result = linearSearch(arr1, key);
        System.out.println((result != -1) ? "Required key: " + key + " found at index:- " + result : "Key " + key + " not found");

        key = 18;
        result = linearSearch(arr1, key);
        System.out.println((result != -1) ? "Required key: " + key + " found at index:- " + result : "Key " + key + " not found");
    }
}

• Detailed breakdown of the linearSearch method:

  • Method signature: public static int linearSearch(int[] inputArray, int key).

  • Parameter inputArray: The array of integers to search.

  • Parameter key: The target integer value being searched for.

  • Loop logic: Iterates with index i from 0 up to inputArray.length - 1.

  • Conditional check: Checks if (inputArray[i] == key). When true, returns i immediately.

  • Fallback return: If loop finishes without returning, the method returns -1.

• Detailed breakdown of main execution:

  • Defines test array arr1 = {5, 9, 10, 2, 90, 4}.

  • Test Case 1 (key = 2):

  • Calls linearSearch(arr1, 2).

  • Returns index 3.

  • Evaluation: (3 != -1) is true, printing: Required key: 2 found at index:- 3.

  • Test Case 2 (key = 18):

  • Calls linearSearch(arr1, 18).

  • Returns -1.

  • Evaluation: (-1 != -1) is false, printing: Key 18 not found.

Searching Algorithms: Binary Search

• Binary Search is an efficient searching algorithm that locates an element in a sorted array by repeatedly dividing the search space in half.

• Strict prerequisite: Binary Search requires that the input array or collection be sorted prior to execution.

• Core algorithmic steps:

  • Step 1: Compare the target key with the middle element of the array.

  • Step 2: If the key matches the middle element, return the middle index immediately.

  • Step 3: If the target key is less than the middle element, narrow the search interval to the lower half (left sublist).

  • Step 4: If the target key is greater than the middle element, narrow the search interval to the upper half (right sublist).

  • Step 5: Repeatedly check from Step 1 until the value is found or the search interval becomes empty (i.e., start > end).

Midpoint Calculation and Integer Overflow Prevention

• Standard Midpoint Formula:   $\text{mid} = \frac{\text{high} + \text{low}}{2}$   or   $\text{mid} = \frac{\text{start} + \text{end}}{2}$

• Integer Overflow Flaw:

  • In standard computer arithmetic, if high and low are large positive integers, their sum (high + low) can exceed the maximum representable signed 32-bit integer limit ($2^{31} - 1 = 2,147,483,647$).

  • Overflow converts the positive sum into a negative integer value, causing array index out-of-bounds exceptions or incorrect execution during midpoint evaluations.

• Overflow-Safe Midpoint Formula:   $\text{mid} = \text{low} + \frac{\text{high} - \text{low}}{2}$

• Mathematical Proof of Equivalence:   $\text{low} + \frac{\text{high} - \text{low}}{2} = \frac{2 \cdot \text{low} + \text{high} - \text{low}}{2} = \frac{\text{high} + \text{low}}{2}$

• Safety Mechanism: Subtracting low from high prior to addition ensures that values remain strictly within valid bound thresholds for non-negative integer values.

Binary Search Step-by-Step Examples and Traces

• Example A: Searching for element 12 in list [10, 12, 20, 32, 50, 55, 65, 80, 99] (indices 0 to 8):

  • Step 1: Compare target 12 with middle element 50 (index 4). Comparison: 12 != 50. Since 12 < 50, restrict search to the left sublist [10, 12, 20, 32] (indices 0 to 3).

  • Step 2: Compare target 12 with middle element 12 of the left sublist (index 1). Comparison: 12 == 12. Target matched. Result: Element found at index 1.

• Example B: Searching for element 80 in list [10, 12, 20, 32, 50, 55, 65, 80, 99] (indices 0 to 8):

  • Step 1: Compare target 80 with middle element 50 (index 4). Comparison: 80 != 50. Since 80 > 50, restrict search to the right sublist [55, 65, 80, 99] (indices 5 to 8).

  • Step 2: Compare target 80 with middle element 65 (index 6). Comparison: 80 != 65. Since 80 > 65, restrict search to the right sublist [80, 99] (indices 7 to 8).

  • Step 3: Compare target 80 with middle element 80 (index 7). Comparison: 80 == 80. Target matched. Result: Element found at index 7.

• Example C: Searching for key 50 in a 7-element array [1, 5, 20, 35, 50, 65, 70] (indices 0 to 6):

  • Initial State: start = 0, end = 6.

  • Step 1: Compute mid = \frac{0 + 6}{2} = 3. Middle element at index 3 is 35. Comparison: $35 < 50$. Select second half (start = 4, end = 6).

  • Step 2: Compute mid = \frac{4 + 6}{2} = 5. Middle element at index 5 is 65. Comparison: $65 > 50$. Select first half of remaining interval (start = 4, end = 4).

  • Step 3: Compute mid = \frac{4 + 4}{2} = 4. Middle element at index 4 is 50. Comparison: $50 == 50$. Target found. Return index 4 (value 50).

• Example D: Searching for target 23 in array [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (indices 0 to 9):

  • Initial State: L = 0, H = 9.

  • Iteration 1: Compute M = \frac{0 + 9}{2} = 4. Element at index 4 is 16. Comparison: $23 > 16$. Take 2nd half (L = 5, H = 9).

  • Iteration 2: Compute M = \frac{5 + 9}{2} = 7. Element at index 7 is 56. Comparison: $23 < 56$. Take 1st half (L = 5, H = 6).

  • Iteration 3: Compute M = \frac{5 + 6}{2} = 5. Element at index 5 is 23. Comparison: $23 == 23$. Found 23, return index 5.

Java Implementation of Binary Search

• The complete Java source code implementation for Binary Search (BinarySearch1) is structured as follows:

public class BinarySearch1 {
    public static int binarySearch(int[] inputArray, int key) {
        int start = 0;
        int end = inputArray.length - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (key == inputArray[mid]) {
                return mid;
            }
            if (key < inputArray[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String args[]) {
        int[] arr1 = {1, 5, 20, 35, 50, 65, 70};
        int key = 100;
        int result = binarySearch(arr1, key);
        System.out.println((result != -1) ? "Required key: " + key + " found at index:- " + result : "Key " + key + " not found");

        key = 50;
        result = binarySearch(arr1, key);
        System.out.println((result != -1) ? "Required key: " + key + " found at index:- " + result : "Key " + key + " not found");
    }
}

• Detailed trace of binarySearch algorithm execution on arr1 = {1, 5, 20, 35, 50, 65, 70}:

  • Execution for Test Case 1 (key = 100):

  • Initial bounds: start = 0, end = 6.

  • Loop iteration 1: start <= end ($0 \le 6$) is true. Calculate mid = (0 + 6) / 2 = 3. inputArray[3] is 35.

    • Check 100 == 35 (false).

    • Check 100 < 35 (false).

    • Else branch taken: start = mid + 1 = 3 + 1 = 4.

  • Loop iteration 2: start <= end ($4 \le 6$) is true. Calculate mid = (4 + 6) / 2 = 5. inputArray[5] is 65.

    • Check 100 == 65 (false).

    • Check 100 < 65 (false).

    • Else branch taken: start = mid + 1 = 5 + 1 = 6.

  • Loop iteration 3: start <= end ($6 \le 6$) is true. Calculate mid = (6 + 6) / 2 = 6. inputArray[6] is 70.

    • Check 100 == 70 (false).

    • Check 100 < 70 (false).

    • Else branch taken: start = mid + 1 = 6 + 1 = 7.

  • Termination check: start <= end ($7 \le 6$) is false. Loop terminates.

  • Function returns -1.

  • Output printed: Key 100 not found.

  • Execution for Test Case 2 (key = 50):

  • Initial bounds: start = 0, end = 6.

  • Loop iteration 1: start <= end ($0 \le 6$) is true. Calculate mid = (0 + 6) / 2 = 3. inputArray[3] is 35.

    • Check 50 == 35 (false).

    • Check 50 < 35 (false).

    • Else branch taken: start = 3 + 1 = 4.

  • Loop iteration 2: start <= end ($4 \le 6$) is true. Calculate mid = (4 + 6) / 2 = 5. inputArray[5] is 65.

    • Check 50 == 65 (false).

    • Check 50 < 65 (true).

    • If branch taken: end = mid - 1 = 5 - 1 = 4.

  • Loop iteration 3: start <= end ($4 \le 4$) is true. Calculate mid = (4 + 4) / 2 = 4. inputArray[4] is 50.

    • Check 50 == 50 (true).

    • Returns index 4 immediately.

  • Output printed: Required key: 50 found at index:- 4.