Seven Searching Algorithms and Ten Sorting Algorithms

The java.util.Arrays class provides utility methods for common operations on arrays:

int[] arr = {1, 2, 3, 4, 5, 7, 8, 9, 10};

// toString: converts array to string representation
Arrays.toString(arr);  // result: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

// binarySearch: binary search for an element
// If the element exists, returns its actual index.
// If not, returns (-(insertion point) - 1).
int index = Arrays.binarySearch(arr, 2);   // returns 1 (since arr[1] == 2)
int index = Arrays.binarySearch(arr, 11);  // returns -11 (insertion point is 10, so -10-1 = -11)

// copyOf: copies array with specified new length
// If new length < old length, partial copy.
// If new length == old length, full copy.
// If new length > old length, extra positions get default values.
int[] newArr1 = Arrays.copyOf(arr, 20);

// copyOfRange: copies a range (from index, inclusive, to index, exclusive)
int[] newArr2 = Arrays.copyOfRange(arr, 0, 9); // copies indices 0..8

// fill: fills entire array with a value
Arrays.fill(arr, 100);  // each element becomes 100

// sort: sorts the array in place
Arrays.sort(arr2);

// Sorting with a custom comparator
Integer[] arr = {2, 3, 1, 5, 6, 7, 8, 4, 9};
// Anonymous inner class (ascending order: o1 - o2)
Arrays.sort(arr, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1 - o2;
    }
});

Lambda Expressions

Lambda expressions enable functional programming by focusing on the action rather than the object performing it.

Arrays.sort(arr, (Integer o1, Integer o2) -> {
    return o1 - o2;
});

Syntax: () -> {}

• () corresponds to method parameters.
• -> is a fixed token.
• {} contains the method body.

Rules:

1. Lambdas can simplify anonymous inner classes.
2. They only work with functional interfaces (enterfaces with exactly one abstract method).
3. The @FunctionalInterface annotation can be used to mark such interfaces.

Lambda Expression Omissions

1. Parameter types can be omitted.
2. If there is only one parameter, both the type and parentheses can be omitted.
3. If the body has only one statement, the braces, semicolon, and return keyword can be omitted together.

Arrays.sort(arr, (o1, o2) -> o1 - o2);

// Example: sort strings by length
String[] arr = {"aaaa", "aaa", "aa"};
Arrays.sort(arr, (o1, o2) -> o1.length() - o2.length());

Collections Framework Hierarchy

• Collection (single-column)
  • List (ordered, duplicates allowed, indexed)
    • ArrayList
    • LinkedList
    • Vector
  • Set (unordered, no duplicates, no index)
    • HashSet
      • LinkedHashSet
    • TreeSet
• Map (double-column) — not covered here

Collection is an interface; common implementations include ArrayList.

Collection<String> coll = new ArrayList<>();

boolean add(E e)
// For List: always returns true.
// For Set: returns true if element added, false if duplicate.

void clear()

boolean remove(Object o)
// Removes a single instance. Returns true if successful.

boolean contains(Object o)
// Uses equals() for comparison. For custom objects, override equals() if needed.

boolean isEmpty()

int size()

Iterating a Collection

Iterator (does not depend on index)

Iterator<E> it = coll.iterator();
while (it.hasNext()) {
    String str = it.next();
    System.out.println(str);
}

Details:

• NoSuchElementException if next() called when no element exists.
• Iterator does not reset automatically.
• Use next() only once per loop iteration.
• Do not call coll.remove() while iterating; use it.remove() instead.

Enhanced for Loop

for (String s : list) {
    System.out.println(s);
}

Modifying the loop variable does not affect the original collection.

Lambda Expression with forEach

coll.forEach(s -> System.out.println(s));

List-Specific Methods

void add(int index, E element)      // inserts at index, shifts elements right
E remove(int index)                 // removes and returns element at index
E set(int index, E element)         // replaces element at index, returns old value
E get(int index)                    // returns element at index

Five Ways to Traverse a List

1. Iterator
2. ListIterator (adds add() method during iteration)
3. Enhanced for
4. Lambda
5. Ordinary for loop

// Iterator
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

// Enhanced for
for (String s : list) {
    System.out.println(s);
}

// Lambda
list.forEach(s -> System.out.println(s));

// Ordinary for
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

// ListIterator
ListIterator<String> it = list.listIterator();
while (it.hasNext()) {
    System.out.println(it.next());
    // it.add("new");  // allowed here
}

Best practice: Use Iterator when removing elements, ListIterator when adding elements, enhanced for or Lambda for simple traversal, ordinary for when index is needed.

ArrayList Internal Mechanics

• Default constructor creates an array of length 0.
• On first add(), a new array of length 10 is allocated.
• When full, the array grows by 1.5×.
• If adding multiple elements exceeds 1.5× capacity, the new array size matches the required capacity.
• size tracks the number of elements and the next insertion index.

LinkedList Internal Mechanics

• Doubly linked list: slow random access, fast insertions/deletions at ends.
• Provides extra methods for manipulating first/last elements.

Generics

Generics (JDK 5+) restrict data types at compile time, accepting only reference types.

// Without generics, all types are Object — losing type safety and requiring casts.
// With generics, type is known at compile time.

// Generic class: type not known until instantiation
public class ArrayList<E> { }

// Generic method: type determined by call
public <T> void show(T t) { }

public static <E> void addAll(ArrayList<E> list, E... elements) {
    for (E elem : elements) {
        list.add(elem);
    }
}

// Generic interface
public interface List<E> { }
// Implementation 1: fix the type
public class MyArrayList implements List<String> { }
// Implementation 2: keep generic
public class MyArrayList<E> implements List<E> { }

Inheritance and Wildcards:

Generics themselves do not support inheritance, but data does. Wildcards ? allow type constraints:

• ? extends E — accepts E or any subclass.
• ? super E — accepts E or any superclass.

public static void method(ArrayList<? extends Ye> list) { }

Set Implementations

• HashSet: unordered, unique, no index.
• LinkedHashSet: insertion-order preserved, unique, no index.
• TreeSet: sorted (natural or custom comparator), unique, no index.

Set<String> s = new HashSet<>();
s.add("a");       // true first time, false if duplicate

// Iteration (all sets):
Iterator<String> it = s.iterator();
while (it.hasNext()) { ... }

for (String str : s) { ... }

s.forEach(str -> System.out.println(str));

HashSet Details

• Backed by a hash table (array + linked list + red-black tree).
• hashCode() returns an int. Default implementation uses memory address; usually overridden to use field values.
• If hashCode() is overridden, objects with equal fields produce the same hash (collisions can still occur).
• Load factor controls when the table resizes.
• Both hashCode() and equals() must be overridden for correct deduplication.

LinkedHashSet

• Extends HashSet with a doubly linked list to maintain insertion order.
• Slightly slower than HashSet; use only when order matters.

TreeSet

• Backed by a red-black tree; elements are sorted.
• Sorting options:
  1. Natural ordering: The element class implements Comparable<T>.
  2. Comparator: Provide a Comparator at construction.

// Natural ordering example: Student implements Comparable<Student>
@Override
public int compareTo(Student o) {
    return this.getAge() - o.getAge();  // ascending age
}

// Comparator (ascending length, then alphabetical)
TreeSet<String> ts = new TreeSet<>((o1, o2) -> {
    int lenDiff = o1.length() - o2.length();
    return lenDiff != 0 ? lenDiff : o1.compareTo(o2);
});

Example with multiple criteria:

@Override
public int compareTo(Student o) {
    int sum1 = this.getChinese() + this.getMath() + this.getEnglish();
    int sum2 = o.getChinese() + o.getMath() + o.getEnglish();
    int i = sum1 - sum2;                       // total score descending? (note: this gives ascending; swap for descending)
    i = (i == 0) ? this.getChinese() - o.getChinese() : i;
    i = (i == 0) ? this.getMath() - o.getMath() : i;
    i = (i == 0) ? this.getEnglish() - o.getEnglish() : i;
    i = (i == 0) ? this.getAge() - o.getAge() : i;
    i = (i == 0) ? this.getName().compareTo(o.getName()) : i;
    return i;
}

Selection Guide:

Requirement	Best Collection	Underlying Structure
Duplicates allowed, general use	ArrayList	Array
Duplicates allowed, many modifications	LinkedList	Linked list
Deduplication (no order)	HashSet	Hash table
Deduplication + insertion order	LinkedHashSet	Hash table + linked list
Deduplication + sorting	TreeSet	Red-black tree (or later sort List)