✅ Solution Implement Both Linear and Binary Search Day 3 DSA with Java

🔹 Linear Search in Java

public class LinearSearch {
    public static int linearSearch(int[] arr, int key) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == key) return i;
        }
        return -1; // Not found
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 2, 9};
        int key = 8;
        int index = linearSearch(arr, key);
        System.out.println("Element found at index: " + index);
    }
}

---

🔹 Binary Search in Java (Iterative)

public class BinarySearch {
    public static int binarySearch(int[] arr, int key) {
        int start = 0, end = arr.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (arr[mid] == key) return mid;
            else if (arr[mid] < key) start = mid + 1;
            else end = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        int key = 5;
        int index = binarySearch(arr, key);
        System.out.println("Element found at index: " + index);
    }
}

---

✅ 2. LeetCode Problems

🔸 Search Insert Position

Problem: Return the index if the target is found. If not, return the index where it would be inserted.

public class SearchInsertPosition {
    public static int searchInsert(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) low = mid + 1;
            else high = mid - 1;
        }
        return low;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 6};
        int target = 2;
        System.out.println("Insert position: " + searchInsert(nums, target));
    }
}

---

🔸 First Bad Version

Assume isBadVersion(version) API exists.

public class FirstBadVersion {
    static int bad = 4; // Let's assume version 4 is the first bad version

    public static boolean isBadVersion(int version) {
        return version >= bad;
    }

    public static int firstBadVersion(int n) {
        int low = 1, high = n;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (isBadVersion(mid)) high = mid;
            else low = mid + 1;
        }
        return low;
    }

    public static void main(String[] args) {
        System.out.println("First bad version: " + firstBadVersion(10));
    }
}

---

🌱 3. Explore: Lower Bound & Upper Bound

These are binary search variants often used in competitive programming.

🔸 Lower Bound (First element ≥ target)

public static int lowerBound(int[] arr, int target) {
    int low = 0, high = arr.length;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] < target) low = mid + 1;
        else high = mid;
    }
    return low; // returns the index
}

🔸 Upper Bound (First element > target)

public static int upperBound(int[] arr, int target) {
    int low = 0, high = arr.length;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] <= target) low = mid + 1;
        else high = mid;
    }
    return low; // returns the index
}

You can test both with:

int[] arr = {1, 3, 3, 5, 7};
System.out.println("Lower Bound of 3: " + lowerBound(arr, 3)); // Output: 1
System.out.println("Upper Bound of 3: " + upperBound(arr, 3)); // Output: 3