Searching Algorithms: Implementation Guide

Linear Search Overview

Linear search is the simplest searching algorithm that works by sequentially checking each element in a collection until the target element is found or the collection is exhausted.

Key Characteristics:

• Time Complexity: O(n) - where n is the number of elements
• Space Complexity: O(1) - constant space used
• Best for: Small datasets, unsorted collections
• Advantage: Works on any collection regardless of order

Implementation Steps

1. 1

   Initialize Search

   Set up array traversal and target value

   public int linearSearch(int[] arr, int target) {
       // Check for null or empty array
       if (arr == null || arr.length == 0) {
           return -1; // Element not found
       }
       
       // Traverse the array
       for (int i = 0; i < arr.length; i++) {
           // Return index when target is found
           if (arr[i] == target) {
               return i;
           }
       }
       
       // Element not found after traversal
       return -1;
   }

2. 2

   Implement Search Logic

   Traverse array and compare elements

   The search logic is straightforward:

   1. Start from the first element (index 0)
   2. Compare current element with the target value
   3. If matched, return the current index
   4. If not matched, move to the next element
   5. Repeat until the end of the array is reached
3. 3

   Handle Edge Cases

   Consider empty arrays and element not found scenarios

   • Null or empty array: Return -1 or throw an exception
   • Element not found: Return -1 or other sentinel value
   • Multiple occurrences: Return first occurrence or all occurrences based on requirements

Visual Example: Linear Search

Let's visualize a linear search for target value 7 in array [5, 2, 9, 7, 3, 1, 6]:

Result: Target found at index 3

Binary Search Overview

Binary search is an efficient algorithm for finding an element in a sorted array. It works by repeatedly dividing the search interval in half.

Key Characteristics:

• Time Complexity: O(log n) - where n is the number of elements
• Space Complexity: O(1) for iterative, O(log n) for recursive implementation
• Requirement: Array must be sorted
• Advantage: Much faster than linear search for large datasets

Implementation Steps

1. 1

   Setup Search Bounds

   Initialize left and right pointers

   public int binarySearch(int[] arr, int target) {
       // Check for null or empty array
       if (arr == null || arr.length == 0) {
           return -1; // Element not found
       }
       
       int left = 0;
       int right = arr.length - 1;
       
       while (left <= right) {
           // Calculate middle index (avoid integer overflow)
           int mid = left + (right - left) / 2;
           
           // Check if target is present at mid
           if (arr[mid] == target) {
               return mid;
           }
           
           // If target is greater, search the right half
           if (arr[mid] < target) {
               left = mid + 1;
           }
           // If target is smaller, search the left half
           else {
               right = mid - 1;
           }
       }
       
       // Element not found
       return -1;
   }

2. 2

   Implement Search Logic

   Use a while loop to narrow down the search range

   The key steps in the binary search algorithm:

   1. Calculate the middle index of the current search range
   2. If the middle element equals the target, return its index
   3. If the middle element is less than the target, search the right half
   4. If the middle element is greater than the target, search the left half
   5. Repeat until the element is found or the search range is empty
3. 3

   Handle Edge Cases

   Consider empty arrays, unsorted arrays, and not found scenarios

   • Null or empty array: Return -1 or throw an exception
   • Unsorted array: Binary search will not work correctly (results are unpredictable)
   • Overflow issues: Use mid = left + (right - left) / 2 instead of mid = (left + right) / 2 to prevent integer overflow

Visual Example: Binary Search

Let's visualize a binary search for target value 42 in array [5, 13, 17, 25, 39, 42, 53, 88]:

Result: Target found at index 5

Recursive Binary Search Implementation

Binary search can also be implemented recursively:

public int binarySearchRecursive(int[] arr, int target) {
    return binarySearchHelper(arr, target, 0, arr.length - 1);
}

private int binarySearchHelper(int[] arr, int target, int left, int right) {
    // Base case: element not found
    if (left > right) {
        return -1;
    }
    
    // Calculate middle index
    int mid = left + (right - left) / 2;
    
    // Check if target is present at mid
    if (arr[mid] == target) {
        return mid;
    }
    
    // If target is greater, search the right half
    if (arr[mid] < target) {
        return binarySearchHelper(arr, target, mid + 1, right);
    }
    
    // If target is smaller, search the left half
    return binarySearchHelper(arr, target, left, mid - 1);
}

Exercise 1: Linear Search

Implement a linear search algorithm to find the index of a given element in an array.

public int linearSearch(int[] arr, int target) {
    // Your implementation here
    // Return the index of the target element or -1 if not found
}

Exercise 2: Binary Search

Implement a binary search algorithm to find the index of a given element in a sorted array.

public int binarySearch(int[] arr, int target) {
    // Your implementation here
    // Return the index of the target element or -1 if not found
}

Exercise 3: Find First and Last Position

Implement a function to find the first and last occurrence of a value in a sorted array.

public int[] searchRange(int[] nums, int target) {
    // Your implementation here
    // Return [firstIndex, lastIndex] or [-1, -1] if not found
}

Hint: Modify the binary search algorithm to find the leftmost and rightmost occurrences.

Exercise 4: Search in Rotated Sorted Array

Implement a search function for a target value in a rotated sorted array (e.g., [4,5,6,7,0,1,2]).

public int search(int[] nums, int target) {
    // Your implementation here
    // Return the index of target or -1 if not found
}

Hint: Determine which half of the array is normally ordered, then check if the target is in that half.

Exercise 5: Jump Search

Implement a jump search algorithm that works by jumping ahead by fixed steps and then using linear search.

public int jumpSearch(int[] arr, int target) {
    // Your implementation here
    // Return the index of target or -1 if not found
}

Hint: Jump size should be approximately √n where n is the array length.