Advanced Java Day 7: Algorithms and Performance Optimization

Goal of this Day

Today you will learn:

• Searching and sorting algorithms: binary search, quicksort, mergesort
• Big-O notation and time/space complexity analysis
• Optimizing loops and memory usage
• Using HashMap for performance improvements

By the end, you will be able to write efficient algorithms and analyze their performance in Java.

Step 1: Sorting Arrays

Use Java’s built-in Arrays.sort() for optimized sorting.

import java.util.Arrays;

int[] arr = {5, 2, 8, 1, 3};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr)); // [1, 2, 3, 5, 8]

Step 2: Searching – Binary Search

Binary search efficiently finds an element in a sorted array.

int index = Arrays.binarySearch(arr, 3);
System.out.println("Index of 3: " + index);

Explanation:

• Array must be sorted
• Divides the search space in half each step → O(log n) time complexity

Step 3: Algorithm Complexity

Big-O notation describes time and space complexity.

• O(n) – linear time
• O(log n) – logarithmic time (binary search)
• O(n log n) – efficient sorting algorithms like mergesort/quicksort
• O(n²) – nested loops / naive algorithms

Step 4: Optimizing Loops and Memory Usage

• Minimize redundant computations inside loops
• Reuse objects when possible to reduce memory allocations
• Prefer HashMap lookups over linear searches for key-value data

Step 5: Using HashMap for Performance

import java.util.*;

Map<String, Integer> map = new HashMap<>();
map.put("Alice", 25);
map.put("Bob", 30);

System.out.println(map.get("Bob")); // 30

Practice

int[] arr = {5, 2, 8, 1, 3};
Arrays.sort(arr); // Built-in optimized sort
System.out.println(Arrays.toString(arr));

Exercise

Implement binary search on a sorted array and analyze time complexity.

Steps:

• Sort the array if not already sorted
• Implement a binary search method
• Return the index of the target element or -1 if not found
• Analyze the algorithm → O(log n)

Example:

import java.util.Arrays;

public class BinarySearchExample {
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(arr[mid] == target) return mid;
            else if(arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 1, 3};
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));

        int index = binarySearch(arr, 3);
        System.out.println("Index of 3: " + index); // 2
    }
}