1. The Hook (The "Byte-Sized" Intro)
In a Nutshell: Searching finds an element's position. Linear search checks one by one (O(N)). Binary search halves the search space each step (O(log N))—but requires sorted data.
When Google searches your contacts: linear for unsorted, binary for sorted alphabetically. Speed matters!
2. Conceptual Clarity
💡 The Analogy
- Linear Search = Checking every book on a shelf
- Binary Search = Dictionary lookup—open to middle, go left/right
3. Technical Mastery
Comparison
| Algorithm | Time | Prerequisite | Use Case |
|---|---|---|---|
| Linear | O(N) | None | Unsorted, small data |
| Binary | O(log N) | Sorted | Large sorted data |
4. Interactive & Applied Code
public class ArraySearching {
public static void main(String[] args) {
int[] unsorted = {64, 25, 12, 22, 11};
int[] sorted = {11, 12, 22, 25, 64};
// === LINEAR SEARCH ===
int target = 22;
int index = linearSearch(unsorted, target);
System.out.println("Linear: Found at index " + index); // 3
// === BINARY SEARCH (iterative) ===
index = binarySearch(sorted, target);
System.out.println("Binary: Found at index " + index); // 2
// === BINARY SEARCH (recursive) ===
index = binarySearchRecursive(sorted, target, 0, sorted.length - 1);
System.out.println("Binary Recursive: " + index);
// === USING Arrays.binarySearch() ===
index = java.util.Arrays.binarySearch(sorted, target);
System.out.println("Arrays.binarySearch: " + index); // 2
// Not found returns -(insertion point) - 1
int notFound = java.util.Arrays.binarySearch(sorted, 15);
System.out.println("Not found: " + notFound); // -3
}
// Linear Search - O(N)
static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // Found!
}
}
return -1; // Not found
}
// Binary Search - O(log N)
static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // Avoid overflow
if (arr[mid] == target) {
return mid; // Found!
} else if (arr[mid] < target) {
left = mid + 1; // Search right half
} else {
right = mid - 1; // Search left half
}
}
return -1; // Not found
}
// Binary Search - Recursive
static int binarySearchRecursive(int[] arr, int target, int left, int right) {
if (left > right) return -1; // Not found
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) return binarySearchRecursive(arr, target, mid + 1, right);
return binarySearchRecursive(arr, target, left, mid - 1);
}
}⚠️ Common Mistakes
Mistake #1: Binary search on unsorted array
int[] unsorted = {5, 2, 8, 1};
Arrays.binarySearch(unsorted, 2); // ❌ Undefined behavior!
// Sort first: Arrays.sort(unsorted);Mistake #2: Integer overflow in mid calculation
int mid = (left + right) / 2; // ❌ Can overflow!
int mid = left + (right - left) / 2; // ✅ SafeMistake #3: Wrong loop condition
while (left < right) // ❌ Misses element when left == right
while (left <= right) // ✅ Correct5. The "Interview Corner"
🏆 Q1: "Binary search time complexity?" Answer: O(log N). Each step halves the search space. For 1 million elements, max 20 comparisons!
🏆 Q2: "Find first/last occurrence in sorted array with duplicates?" Answer: Modify binary search—when found, continue left (first) or right (last) instead of returning immediately.
🏆 Q3: "What does Arrays.binarySearch return if not found?"
Answer: -(insertion point) - 1. If element would be at index 3, returns -4.
🎓 Key Takeaways
✅ Linear: O(N), works on any array
✅ Binary: O(log N), requires sorted
✅ Use left + (right-left)/2 to avoid overflow
✅ Arrays.binarySearch() for built-in solution
✅ Always sort before binary search!