✅ Day 3: Searching Algorithms in Java

🎯 Goals:

• Understand Linear Search and Binary Search

• Learn when and how to use each

• Solve real interview problems using searching techniques

---

🔍 1. Linear Search

📘 Definition:

Linearly checks each element one by one. Used when the array is unsorted.

✅ Code Example:

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
}

---

🧠 2. Binary Search

📘 Definition:

Used on sorted arrays. It divides the search space in half each time — O(log N) time complexity.

✅ Code (Iterative Approach):

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;
}

✅ Code (Recursive Approach):

public static int binarySearchRec(int[] arr, int key, int start, int end) {
    if (start > end) return -1;

    int mid = start + (end - start) / 2;
    if (arr[mid] == key) return mid;
    else if (arr[mid] < key) return binarySearchRec(arr, key, mid + 1, end);
    else return binarySearchRec(arr, key, start, mid - 1);
}

---

💡 3. Binary Search Use Cases

• Search in sorted array

• Find first/last occurrence of an element

• Search in rotated sorted arrays

• Peak elements in mountain arrays

---

✍️ 4. Practice Problems

🔹 Write functions to:

• Find first and last occurrence of an element (e.g. in sorted duplicates)

• Count how many times a number appears in sorted array

• Search in a rotated sorted array

• Find square root using binary search (approximate to floor)

---

🔥 5. BONUS – Search in 2D Matrix

🔹 Use binary search logic on 2D:

public static boolean searchMatrix(int[][] matrix, int target) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int low = 0, high = rows * cols - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        int value = matrix[mid / cols][mid % cols];

        if (value == target) return true;
        else if (value < target) low = mid + 1;
        else high = mid - 1;
    }
    return false;
}

---

📚 Homework for Day 3:

• Implement both linear and binary search

• Solve 2 problems from LeetCode:

  • Search Insert Position

  • First Bad Version

• Explore: Lower Bound, Upper Bound (optional but forward-thinking)

---

⏭️ What’s Coming on Day 4?

• Sorting Algorithms: Bubble, Selection, Insertion (with time/space analysis)