binarySearch() on Unsorted Arrays — Silent Index Corruption

package io.thecodeforge.search;

public class LinearSearchDemo {

    /**
     * Searches for a target score in an array of exam scores.
     * Returns the index of the target if found, or -1 if not found.
     *
     * @param scores  the array to search through
     * @param target  the score we are looking for
     * @return        the index of the target, or -1
     */
    public static int linearSearch(int[] scores, int target) {
        // Loop through every position in the array, one by one
        for (int index = 0; index < scores.length; index++) {

            // Check if the current element matches our target
            if (scores[index] == target) {
                return index; // Found it! Return its position immediately
            }
        }

        // We checked every element and never found the target
        return -1;
    }

    public static void main(String[] args) {
        // A small class of students' exam scores — NOT sorted on purpose
        int[] examScores = {72, 85, 91, 60, 78, 95, 88, 67};

        int targetScore = 95;
        int notPresentScore = 50;

        // --- Search 1: Looking for a score that EXISTS in the array ---
        int foundIndex = linearSearch(examScores, targetScore);

        if (foundIndex != -1) {
            // foundIndex holds the real position (0-based)
            System.out.println("Score " + targetScore + " found at index " + foundIndex);
        } else {
            System.out.println("Score " + targetScore + " was not found.");
        }

        // --- Search 2: Looking for a score that does NOT exist ---
        int missingIndex = linearSearch(examScores, notPresentScore);

        if (missingIndex != -1) {
            System.out.println("Score " + notPresentScore + " found at index " + missingIndex);
        } else {
            // -1 is our signal that the target was never found
            System.out.println("Score " + notPresentScore + " was not found in the array.");
        }

        // --- Show how many comparisons worst-case would require ---
        System.out.println("\nArray has " + examScores.length + " elements.");
        System.out.println("Worst case: " + examScores.length + " comparisons (linear search).");
    }
}

package io.thecodeforge.search;

import java.util.Arrays; // Needed for Arrays.sort() and Arrays.binarySearch()

public class BinarySearchDemo {

    /**
     * Manual binary search implementation so you can see exactly what happens.
     * IMPORTANT: the array passed in MUST already be sorted ascending.
     *
     * @param sortedPrices  a sorted array of product prices
     * @param targetPrice   the price we are searching for
     * @return              the index of the target, or -1 if not found
     */
    public static int manualBinarySearch(int[] sortedPrices, int targetPrice) {
        int leftBoundary  = 0;                        // Start of the search zone
        int rightBoundary = sortedPrices.length - 1; // End of the search zone

        while (leftBoundary <= rightBoundary) {
            // Calculate the midpoint — avoid integer overflow with this formula
            int midpoint = leftBoundary + (rightBoundary - leftBoundary) / 2;

            System.out.println("  Checking index " + midpoint
                    + " (value: " + sortedPrices[midpoint] + ")");

            if (sortedPrices[midpoint] == targetPrice) {
                return midpoint; // Exact match — return position

            } else if (sortedPrices[midpoint] < targetPrice) {
                // The target is in the RIGHT half — discard everything left of midpoint
                leftBoundary = midpoint + 1;

            } else {
                // The target is in the LEFT half — discard everything right of midpoint
                rightBoundary = midpoint - 1;
            }
        }

        return -1; // Target not found
    }

    public static void main(String[] args) {
        // Product prices — we sort them FIRST so binary search can work
        int[] productPrices = {499, 120, 850, 35, 670, 250, 15, 980};

        System.out.println("=== Manual Binary Search ===\n");

        // Step 1: Sort the array — binary search REQUIRES this
        Arrays.sort(productPrices);
        System.out.println("Sorted prices: " + Arrays.toString(productPrices));

        // Step 2: Search for a price that exists
        int targetPrice = 250;
        System.out.println("\nSearching for price: " + targetPrice);
        int manualResult = manualBinarySearch(productPrices, targetPrice);

        if (manualResult != -1) {
            System.out.println("Found at index: " + manualResult);
        } else {
            System.out.println("Price not found.");
        }

        // Step 3: Search for a price that does NOT exist
        int missingPrice = 300;
        System.out.println("\nSearching for price: " + missingPrice);
        int missingResult = manualBinarySearch(productPrices, missingPrice);
        System.out.println(missingResult != -1
                ? "Found at index: " + missingResult
                : "Price not found.");

        // ---------------------------------------------------------------
        System.out.println("\n=== Java Built-in Arrays.binarySearch() ===\n");

        // Arrays.binarySearch() does the same job — use this in real code
        // The array must STILL be sorted before calling it
        int builtInResult = Arrays.binarySearch(productPrices, targetPrice);

        if (builtInResult >= 0) {
            // A positive (or zero) result means it was found
            System.out.println("Arrays.binarySearch() found " + targetPrice
                    + " at index: " + builtInResult);
        } else {
            // A negative result means it was NOT found
            System.out.println("Arrays.binarySearch() did not find " + targetPrice);
        }

        // Check for a missing value with the built-in method
        int builtInMissing = Arrays.binarySearch(productPrices, missingPrice);
        System.out.println("Result for missing price " + missingPrice
                + ": " + builtInMissing + " (negative = not found)");
    }
}

See table above

package io.thecodeforge.search;

import java.util.Arrays;

public class RecursiveBinarySearchDemo {

    /**
     * Recursive binary search.
     * @param arr sorted array
     * @param target value to find
     * @param low left boundary (inclusive)
     * @param high right boundary (inclusive)
     * @return index of target, or -1 if not found
     */
    public static int recursiveBinarySearch(int[] arr, int target, int low, int high) {
        // Base case: search space is empty
        if (low > high) {
            return -1;
        }

        int mid = low + (high - low) / 2;  // avoid overflow

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            // Search right half
            return recursiveBinarySearch(arr, target, mid + 1, high);
        } else {
            // Search left half
            return recursiveBinarySearch(arr, target, low, mid - 1);
        }
    }

    // Convenience wrapper
    public static int recursiveBinarySearch(int[] arr, int target) {
        return recursiveBinarySearch(arr, target, 0, arr.length - 1);
    }

    public static void main(String[] args) {
        int[] sorted = {10, 20, 30, 40, 50, 60, 70};
        System.out.println("Sorted array: " + Arrays.toString(sorted));

        for (int t : new int[]{20, 55, 70}) {
            int idx = recursiveBinarySearch(sorted, t);
            System.out.println("Search " + t + ": " + (idx >= 0 ? "Found at " + idx : "Not found"));
        }
    }
}

package io.thecodeforge.search;

import java.util.Arrays;

public class AdvancedSearchDemo {

    // Jump Search: O(√n), requires sorted array
    public static int jumpSearch(int[] arr, int target) {
        int n = arr.length;
        int blockSize = (int) Math.sqrt(n);
        int prev = 0;
        // Jump forward in blocks
        while (arr[Math.min(blockSize, n) - 1] < target) {
            prev = blockSize;
            blockSize += (int) Math.sqrt(n);
            if (prev >= n) return -1;
        }
        // Linear search within the block
        for (int i = prev; i < Math.min(blockSize, n); i++) {
            if (arr[i] == target) return i;
        }
        return -1;
    }

    // Interpolation Search: O(log log n) average, worst O(n), requires sorted uniformly distributed data
    public static int interpolationSearch(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        while (low <= high && target >= arr[low] && target <= arr[high]) {
            if (low == high) {
                if (arr[low] == target) return low;
                else return -1;
            }
            // Formula to estimate position
            int pos = low + (((high - low) * (target - arr[low])) / (arr[high] - arr[low]));
            if (arr[pos] == target) return pos;
            if (arr[pos] < target) low = pos + 1;
            else high = pos - 1;
        }
        return -1;
    }

    // Exponential Search: O(log n), good for unbounded arrays
    public static int exponentialSearch(int[] arr, int target) {
        if (arr[0] == target) return 0;
        int bound = 1;
        while (bound < arr.length && arr[bound] <= target) {
            bound *= 2;
        }
        // Binary search between bound/2 and min(bound, arr.length-1)
        int low = bound / 2;
        int high = Math.min(bound, arr.length - 1);
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == target) return mid;
            if (arr[mid] < target) low = mid + 1;
            else high = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50, 60, 70};
        System.out.println("Array: " + Arrays.toString(arr));
        System.out.println("Jump Search 50: " + jumpSearch(arr, 50));
        System.out.println("Interpolation Search 30: " + interpolationSearch(arr, 30));
        System.out.println("Exponential Search 70: " + exponentialSearch(arr, 70));
    }
}

package io.thecodeforge.search;

import java.util.Arrays;

public class StringArraySearchDemo {

    /**
     * Linear search for a username — works on unsorted arrays.
     * Uses .equalsIgnoreCase() so 'Alice' and 'alice' both match.
     */
    public static int findUsername(String[] usernames, String targetUsername) {
        for (int index = 0; index < usernames.length; index++) {
            // .equalsIgnoreCase() compares content, not memory address
            if (usernames[index].equalsIgnoreCase(targetUsername)) {
                return index;
            }
        }
        return -1;
    }

    public static void main(String[] args) {

        // --- Scenario 1: Unsorted list — use linear search ---
        String[] activeUsers = {"priya", "marco", "alice", "leon", "yuki"};

        System.out.println("=== Linear Search on Unsorted String Array ===\n");

        String searchName = "Alice"; // Different capitalisation — test .equalsIgnoreCase()
        int linearResult = findUsername(activeUsers, searchName);

        if (linearResult != -1) {
            System.out.println("'" + searchName + "' found at index " + linearResult
                    + " (stored as '" + activeUsers[linearResult] + "')");
        } else {
            System.out.println("'" + searchName + "' not found.");
        }

        // Demonstrate the == trap so you can see exactly why it fails
        System.out.println("\n--- The String == Trap (DO NOT DO THIS) ---");
        String builtFromChars = new String("priya"); // Deliberately a new object
        System.out.println("Using == :      " + (activeUsers[0] == builtFromChars));       // false — wrong!
        System.out.println("Using .equals(): " + activeUsers[0].equals(builtFromChars)); // true  — correct

        // --- Scenario 2: Sorted list — use Arrays.binarySearch() ---
        System.out.println("\n=== Binary Search on Sorted String Array ===\n");

        String[] sortedUsernames = {"alice", "leon", "marco", "priya", "yuki"};
        System.out.println("Sorted usernames: " + Arrays.toString(sortedUsernames));

        String loginAttempt = "marco";
        // Arrays.binarySearch() on Strings is case-sensitive
        int binaryResult = Arrays.binarySearch(sortedUsernames, loginAttempt);

        if (binaryResult >= 0) {
            System.out.println("Login approved: '" + loginAttempt
                    + "' found at index " + binaryResult);
        } else {
            System.out.println("Login denied: '" + loginAttempt + "' not found.");
        }

        // What happens if we search with wrong capitalisation?
        String wrongCase = "Marco"; // Capital M
        int wrongCaseResult = Arrays.binarySearch(sortedUsernames, wrongCase);
        System.out.println("\nSearching for '" + wrongCase + "' (capital M): result = "
                + wrongCaseResult + " — negative means not found!");
        System.out.println("Tip: Normalise to lowercase before sorting AND before searching.");
    }
}

package io.thecodeforge.search;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CollectionsBinarySearchDemo {

    public static void main(String[] args) {
        // Build an ArrayList of exam scores (unsorted)
        List<Integer> scores = new ArrayList<>();
        scores.add(85);
        scores.add(72);
        scores.add(91);
        scores.add(60);
        scores.add(78);

        System.out.println("Original list: " + scores);

        // Sort first — required for binary search
        Collections.sort(scores);
        System.out.println("Sorted list:   " + scores);

        // Search for an existing score
        Integer target = 78;
        int index = Collections.binarySearch(scores, target);

        if (index >= 0) {
            System.out.println("Found " + target + " at index " + index);
        } else {
            System.out.println(target + " not found. Insertion point: " + (-(index + 1)));
        }

        // Search for a missing score
        int missingIndex = Collections.binarySearch(scores, 100);
        System.out.println("Search for 100: " + missingIndex + " (negative = not found)");
    }
}

# --- Linear Search ---
def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

# --- Binary Search (manual, iterative) ---
def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# --- Using Python's bisect module ---
import bisect
def binary_search_bisect(arr, target):
    # bisect_left returns insertion point; check if target exists
    i = bisect.bisect_left(arr, target)
    if i != len(arr) and arr[i] == target:
        return i
    return -1

# Demo
arr = [10, 20, 30, 40, 50]
print("Linear search 30:", linear_search(arr, 30))
print("Binary search 40:", binary_search(arr, 40))
print("bisect search 50:", binary_search_bisect(arr, 50))

# JavaScript implementation (conceptually)
/*
function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return -1;
}

function binarySearch(arr, target) {
    let low = 0, high = arr.length - 1;
    while (low <= high) {
        const mid = Math.floor(low + (high - low) / 2);
        if (arr[mid] === target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}
*/

// io.thecodeforge — java tutorial

import java.util.Arrays;

public class BinarySearchSyntaxDemo {
    public static void main(String[] args) {
        int[] scores = {55, 72, 88, 91, 97};
        int existing = Arrays.binarySearch(scores, 88);
        int missing = Arrays.binarySearch(scores, 80);
        
        System.out.println("Found 88 at index: " + existing);
        System.out.println("Missing 80 returns: " + missing);
        // Restore insertion point: -missing - 1
        int insertionPoint = -missing - 1;
        System.out.println("Insertion point for 80: " + insertionPoint);
    }
}

// io.thecodeforge — java tutorial

import java.util.Arrays;

public class MultiTypeBinarySearch {
    public static void main(String[] args) {
        // Primitives
        int[] ids = {101, 203, 307, 412};
        System.out.println("Int search 307: " + Arrays.binarySearch(ids, 307));
        
        char[] initials = {'A', 'D', 'K', 'M'};
        System.out.println("Char search 'K': " + Arrays.binarySearch(initials, 'K'));
        
        double[] prices = {29.99, 34.50, 49.99, 99.99};
        System.out.println("Double search 34.50: " + Arrays.binarySearch(prices, 34.50));
        
        // Object array — strings use natural order
        String[] names = {"Alice", "Bob", "Carol", "Dave"};
        System.out.println("String search 'Carol': " + Arrays.binarySearch(names, "Carol"));
    }
}

// io.thecodeforge — java tutorial
public class ArraySearchSolution {
    public static int search(int[] arr, int target) {
        // Always check if sorted first — binary search only works on sorted data
        if (isSorted(arr)) {
            int result = java.util.Arrays.binarySearch(arr, target);
            return result >= 0 ? result : -1; // Map negative to -1 for consistency
        }
        // Fallback to linear search for unsorted arrays
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) return i;
        }
        return -1;
    }
    private static boolean isSorted(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i - 1]) return false;
        }
        return true;
    }
    public static void main(String[] args) {
        int[] data = {1, 3, 5, 7, 9};
        int found = search(data, 5); // Returns 2
        System.out.println(found);
    }
}

// io.thecodeforge — java tutorial
public class SearchDecisionExample {
    public static void main(String[] args) {
        int[] tiny = {4, 2, 7, 1, 9}; // Unsorted, small
        int[] sortedHuge = new int[100_000];
        java.util.Arrays.setAll(sortedHuge, i -> i * 2); // Sorted, large
        // Single search on tiny → linear
        System.out.println("Linear: " + linearFind(tiny, 7));
        // Multiple searches on huge → sort + binary
        long start = System.nanoTime();
        for (int i = 0; i < 1000; i++) {
            java.util.Arrays.binarySearch(sortedHuge, i * 2);
        }
        System.out.println("Binary elapsed ns: " + (System.nanoTime() - start));
    }
    static int linearFind(int[] arr, int key) {
        for (int i = 0; i < arr.length; i++) if (arr[i] == key) return i;
        return -1;
    }
}