Binary Search Fundamentals

Binary search oeprates on sorted arrays to locate target values efficiently.

public class BinarySearch {
    public int findTarget(int[] sortedArray, int target) {
        int start = 0;
        int end = sortedArray.length - 1;
        
        while (start <= end) {
            int center = start + (end - start) / 2;
            
            if (sortedArray[center] < target) {
                start = center + 1;
            } else if (sortedArray[center] > target) {
                end = center - 1;
            } else {
                return center;
            }
        }
        return -1;
    }
}

Finding Insertion Position

Determines where to insert a target value while maintaining array order.

public class InsertPosition {
    public int findInsertIndex(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        
        while (low < high) {
            int middle = low + (high - low) / 2;
            
            if (nums[middle] < target) {
                low = middle + 1;
            } else if (nums[middle] > target) {
                high = middle - 1;
            } else {
                return middle;
            }
        }
        
        return nums[low] >= target ? low : low + 1;
    }
}

Number Guessing Algorithm

Implements binary search with a guessing function interface.

public class NumberGuesser extends GuessGame {
    public int guessNumber(int maxValue) {
        int lowBound = 1;
        int highBound = maxValue;
        
        while (lowBound < highBound) {
            int midpoint = lowBound + (highBound - lowBound) / 2;
            
            if (guess(midpoint) <= 0) {
                highBound = midpoint;
            } else {
                lowBound = midpoint + 1;
            }
        }
        
        return lowBound;
    }
}

Integer Square Root Calculation

Computes the integer square root using binary search.

public class SquareRootCalculator {
    public int calculateSqrt(int number) {
        int left = 0;
        int right = number;
        int result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if ((long) mid * mid <= number) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
}

Two Sum in Sorted Array

Finds two numbers that add up to a target in a sorted array.

public class TwoSumFinder {
    public int[] findTwoSum(int[] numbers, int targetSum) {
        int leftIndex = 0;
        int rightIndex = numbers.length - 1;
        
        while (leftIndex < rightIndex) {
            int currentSum = numbers[leftIndex] + numbers[rightIndex];
            
            if (currentSum < targetSum) {
                leftIndex++;
            } else if (currentSum > targetSum) {
                rightIndex--;
            } else {
                return new int[]{leftIndex + 1, rightIndex + 1};
            }
        }
        
        return new int[]{-1, -1};
    }
}

Package Shipping Capacity Optimization

Determines minimum shipping capacity to deliver packages within days.

public class ShippingCapacity {
    public int calculateMinimumCapacity(int[] packageWeights, int deadlineDays) {
        int minCapacity = Arrays.stream(packageWeights).max().getAsInt();
        int maxCapacity = Arrays.stream(packageWeights).sum();
        
        while (minCapacity < maxCapacity) {
            int daysRequired = 1;
            int currentLoad = 0;
            int testCapacity = minCapacity + (maxCapacity - minCapacity) / 2;
            
            for (int weight : packageWeights) {
                if (currentLoad + weight > testCapacity) {
                    daysRequired++;
                    currentLoad = 0;
                }
                currentLoad += weight;
            }
            
            if (daysRequired <= deadlineDays) {
                maxCapacity = testCapacity;
            } else {
                minCapacity = testCapacity + 1;
            }
        }
        
        return minCapacity;
    }
}

First Bad Version Detection

Identifies the first faulty version in a version sequence.

public class VersionChecker extends VersionControl {
    public int locateFirstBadVersion(int totalVersions) {
        int firstVersion = 1;
        int lastVersion = totalVersions;
        
        while (firstVersion < lastVersion) {
            int midVersion = firstVersion + (lastVersion - firstVersion) / 2;
            
            if (!isBadVersion(midVersion)) {
                firstVersion = midVersion + 1;
            } else {
                lastVersion = midVersion;
            }
        }
        
        return firstVersion;
    }
}

Array Stream Operations

Utility methods for array analysis using streams.

public class ArrayAnalyzer {
    private static int[] sampleArray = {30, 96, 23, 69, 85, 62, 12, 99, 11};
    
    public static void analyzeArray() {
        int total = Arrays.stream(sampleArray).sum();
        int maximum = Arrays.stream(sampleArray).max().getAsInt();
        int minimum = Arrays.stream(sampleArray).min().getAsInt();
        double average = Arrays.stream(sampleArray).average().getAsDouble();
        
        System.out.println("Maximum: " + maximum);
        System.out.println("Minimum: " + minimum);
        System.out.println("Total: " + total);
        System.out.println("Average: " + average);
    }
}