Arrays

The Nature of Arrays in Java:

An Array is an indexed collection of elements of the same data type (homogeneous) allocated in contiguous memory blocks on the Heap. In Java, arrays are true objects, instantiated using the new operator.

Three Stages of Array Creation:

1. Declaration: int[] arr; (Creates a reference variable on the Stack; currently null).
2. Instantiation: arr = new int[5]; (Allocates contiguous Heap memory for 5 integers initialized to 0).
3. Initialization: Populating values individually (arr[0] = 10;) or via inline array literal (int[] arr = {10, 20, 30, 40, 50};).

Sequential Scanning Logic:

Linear Search compares the target search key sequentially against every element in the array from index $0$ up to $N - 1$. It requires NO precondition (the array can be completely unsorted).

public static int linearSearch(int[] arr, int key) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == key) {
            return i; // Target found at index i!
        }
    }
    return -1; // Target not present in array
}

Algorithmic Complexity:

• Best Case: $O(1)$ (Key found at index 0 on first comparison).
• Worst Case: $O(n)$ (Key located at the final index or absent from the array).

Divide-and-Conquer Search on Sorted Data:

Binary Search is an exceptionally fast searching algorithm that operates on the fundamental precondition that the array MUST be sorted (either in ascending or descending order). In each iteration, it compares the target key with the middle element ($mid = (low + high) / 2$):

• If key == arr[mid]: Search terminates successfully.
• If key < arr[mid]: Search space is restricted to the left half (high = mid - 1).
• If key > arr[mid]: Search space is restricted to the right half (low = mid + 1).

public static int binarySearch(int[] arr, int key) {
    int low = 0, high = arr.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == key) return mid;
        else if (key < arr[mid]) high = mid - 1;
        else low = mid + 1;
    }
    return -1; // Not found
}

Efficiency: Time complexity is $O(\log_2 n)$. In an array of $1,000,000$ elements, binary search requires at most $20$ comparisons, whereas linear search requires up to $1,000,000$!

Bubble Sort Principle:

In Bubble Sort, the array is traversed multiple times. In each pass, adjacent elements are compared ($arr[j]$ and $arr[j+1]$); if they are out of order ($arr[j] > arr[j+1]$), they are swapped. As a result, the largest element in the unsorted segment "bubbles up" to its final position at the end of the array.

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {           // Outer loop: n - 1 passes
        for (int j = 0; j < n - 1 - i; j++) {   // Inner loop: comparisons
            if (arr[j] > arr[j + 1]) {
                // Swap adjacent elements
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Selection Sort Principle:

In Selection Sort, the algorithm divides the array into a sorted prefix and an unsorted suffix. In each pass $i$, it scans the unsorted segment to find the index of the minimum element and swaps it with the element at position $i$.

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j; // Update index of minimum
            }
        }
        // Swap minimum element with element at index i
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

Matrix Structure in Java:

A 2D array is an array of arrays representing a grid with $M$ rows and $N$ columns:

int[][] matrix = new int[4][4]; // 4x4 matrix

Geometrical Index Formulas for Square Matrices ($N \times N$):

Model Program 1: Input, Bubble Sort & Binary Search on 15 Students' Marks

import java.util.Scanner;

public class StudentMarksArray {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] marks = new int[15];

        System.out.println("Enter marks for 15 students:");
        for (int i = 0; i < marks.length; i++) {
            System.out.print("Student " + (i + 1) + ": ");
            marks[i] = sc.nextInt();
        }

        // 1. Sort using Bubble Sort
        for (int i = 0; i < marks.length - 1; i++) {
            for (int j = 0; j < marks.length - 1 - i; j++) {
                if (marks[j] > marks[j + 1]) {
                    int temp = marks[j];
                    marks[j] = marks[j + 1];
                    marks[j + 1] = temp;
                }
            }
        }

        System.out.println("
Sorted Marks (Ascending Order):");
        for (int m : marks) {
            System.out.print(m + " ");
        }
        System.out.println();

        // 2. Search using Binary Search
        System.out.print("
Enter mark to search: ");
        int searchKey = sc.nextInt();

        int low = 0, high = marks.length - 1, foundIndex = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (marks[mid] == searchKey) {
                foundIndex = mid;
                break;
            } else if (searchKey < marks[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        if (foundIndex != -1) {
            System.out.println("Search Successful! Mark " + searchKey + " found at sorted position " + (foundIndex + 1));
        } else {
            System.out.println("Search Unsuccessful: Mark " + searchKey + " is not present.");
        }
    }
}

Model Program 2: 4x4 Matrix Diagonals Summation & Transpose Display

import java.util.Scanner;

public class MatrixAnalysis {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[][] a = new int[4][4];

        System.out.println("Enter elements for 4x4 matrix:");
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                a[i][j] = in.nextInt();
            }
        }

        int leftDiagonalSum = 0;
        int rightDiagonalSum = 0;

        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (i == j) leftDiagonalSum += a[i][j];
                if (i + j == 3) rightDiagonalSum += a[i][j];
            }
        }

        System.out.println("
Original Matrix:");
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                System.out.print(a[i][j] + "	");
            }
            System.out.println();
        }

        System.out.println("
Left Diagonal Sum : " + leftDiagonalSum);
        System.out.println("Right Diagonal Sum: " + rightDiagonalSum);

        System.out.println("
Transpose of Matrix (Rows swapped with Columns):");
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                System.out.print(a[j][i] + "	"); // Row-column transposed!
            }
            System.out.println();
        }
    }
}