Searching and Sorting Algorithms in Java

Binary Search in Java (Iterative Version)

Uses a loop to repeatedly divide the search range in half. Terminates when the element is found or the range is reduced to zero. Complexity: O(logn). Space Complexity: O(1) (constant space).

Binary Search in Java (Recursive Version)

Uses recursion to divide the search range in half at each call. Recursion stops when the element is found or when the base case is reached (range becomes invalid). Complexity: O(logn). Space Complexity: O(logn) due to recursive call stack.

Linear Search in Java

Iterates through each element in the array until the desired value is found or the array ends. Best Use: For unsorted arrays or when the list is small. Complexity: O(n). Space Complexity: O(1) (constant space).

Selection Sort in Java

Finds the smallest element and swaps it with the first unsorted element, repeatedly moving through the list. In-place: Yes. Stability: Not stable (relative order of equal elements might not be preserved). Complexity: O(n^2). Space Complexity: O(1).

Insertion Sort in Java (Shifting Version)

Elements are shifted to their correct position rather than swapped. The key is inserted at the appropriate position. In-place: Yes. Stability: Stable. Complexity: O(n^2). Space Complexity: O(1). Best Use: Small or mostly sorted datasets.

Insertion Sort in Java (Swapping Version)

Compares each element with the elements to its left and swaps them into the correct position. In-place: Yes. Stability: Stable. Complexity: O(n^2). Space Complexity: O(1). Best Use: Small or mostly sorted datasets.

Merge Sort in Java

Divide the array into halves, recursively sort them, and then merge the sorted halves. In-place: No (uses auxiliary array for merging). Stability: Stable. Complexity: O(nlogn). Space Complexity: O(n) (extra space for merging).

Bubble Sort in Java

Repeatedly swaps adjacent elements if they are in the wrong order, moving the largest elements to the end. In-place: Yes. Stability: Stable. Complexity: O(n^2). Space Complexity: O(1). Best Use: Simple sorting of small arrays.

Quick Sort in Java

Selects a pivot, partitions the array into two sub-arrays (elements less than the pivot and elements greater), then recursively sorts the sub-arrays. In-place: Yes. Stability: Not stable. Complexity: O(nlogn) on average, O(n^2) in worst case. Space Complexity: O(logn) due to recursion (or iterative versions can be O(1)).