Searching Problems

Posted on: February 1, 2025 Posted by: rahulgite Comments: 0

Problem 1: Search Insert Position

Explanation:

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be inserted in order.

Approach:

  1. Binary Search: Use binary search to efficiently find the insertion position.
  2. Compare Midpoint: If nums[mid] equals the target, return mid. Otherwise, adjust the search boundaries.
  3. Return Left Pointer: After the loop, left will be at the correct insertion position.

Time & Space Complexity:

  • Time Complexity: O(log n), as binary search reduces the problem size by half at each step.
  • Space Complexity: O(1), since we use only a few extra variables.

Java Implementation:

public class SearchInsertPosition {
    /**
     * Finds the index where the target should be inserted.
     * @param nums sorted input array
     * @param target value to search for
     * @return index of target or insertion position
     * 
     * Time Complexity: O(log n) - Binary search halves the search space.
     * Space Complexity: O(1) - No additional space is used.
     */
    public static int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
    
    public static void main(String[] args) {
        int[] input = {1, 3, 5, 6};
        int target = 5;
        int output = searchInsert(input, target);
        System.out.println("Output: " + output);
    }
}

Example:

Input:

nums = [1,3,5,6], target = 5

Output:

2

Edge Cases Considered:

  • Target is smaller than all elements → Insert at index 0.
  • Target is larger than all elements → Insert at the last index.
  • Target is between elements → Binary search finds the position.
  • Empty array → Should return 0.

Problem 2: Binary Search

Explanation:

Given a sorted array of integers and a target value, return the index of the target if found. Otherwise, return -1.

Approach:

  1. Binary Search: Start with two pointers, left at 0 and right at n - 1.
  2. Check Midpoint:
    • If nums[mid] == target, return mid.
    • If nums[mid] < target, adjust left.
    • If nums[mid] > target, adjust right.
  3. Return -1 if Not Found: If left exceeds right, return -1.

Time & Space Complexity:

  • Time Complexity: O(log n), as binary search halves the search space.
  • Space Complexity: O(1), as no extra space is used.

Java Implementation:

public class BinarySearch {
    /**
     * Performs binary search to find the target index.
     * @param nums sorted input array
     * @param target value to search for
     * @return index of target or -1 if not found
     * 
     * Time Complexity: O(log n) - Binary search halves the search space.
     * Space Complexity: O(1) - No additional space is used.
     */
    public static int binarySearch(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        int[] input = {-1, 0, 3, 5, 9, 12};
        int target = 9;
        int output = binarySearch(input, target);
        System.out.println("Output: " + output);
    }
}

Example:

Input:

nums = [-1,0,3,5,9,12], target = 9

Output:

4

Edge Cases Considered:

  • Target is the first element → Should return 0.
  • Target is the last element → Should return n - 1.
  • Target is not in array → Should return -1.
  • Empty array → Should return -1.

Problem 3: Search in Rotated Sorted Array

Explanation:

Given a rotated sorted array and a target value, return the index of the target if found. Otherwise, return -1.

Approach:

  1. Binary Search Adaptation: The array is rotated, so we must determine which half is sorted.
  2. Determine Sorted Half:
    • If nums[left] <= nums[mid], the left half is sorted.
    • Otherwise, the right half is sorted.
  3. Adjust Search Range:
    • If the target is in the sorted half, adjust left and right accordingly.
    • Otherwise, search in the other half.
  4. Continue Until Found or Exhausted: If left exceeds right, return -1.

Time & Space Complexity:

  • Time Complexity: O(log n), since binary search is applied.
  • Space Complexity: O(1), as no extra space is used.

Java Implementation:

public class SearchRotatedSortedArray {
    /**
     * Searches for a target in a rotated sorted array.
     * @param nums rotated sorted input array
     * @param target value to search for
     * @return index of target or -1 if not found
     * 
     * Time Complexity: O(log n) - Binary search approach.
     * Space Complexity: O(1) - No extra space used.
     */
    public static int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[left] <= nums[mid]) { // Left half is sorted
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else { // Right half is sorted
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        int[] input = {4,5,6,7,0,1,2};
        int target = 0;
        int output = search(input, target);
        System.out.println("Output: " + output);
    }
}

Example:

Input:

nums = [4,5,6,7,0,1,2], target = 0

Output:

4

Edge Cases Considered:

  • Target is in the rotated part → Algorithm correctly adjusts.
  • Target is in the sorted part → Binary search finds it.
  • Array contains only one element → Should return 0 if found, -1 otherwise.
  • Empty array → Should return -1.

Problem 4: Find First and Last Position of Element in Sorted Array

Explanation:

Given a sorted array of integers and a target value, return the first and last index of the target. If the target is not found, return [-1, -1].

Approach:

  1. Binary Search for First Occurrence:
    • Perform binary search to find the first occurrence of target.
    • If nums[mid] matches target, continue searching left.
  2. Binary Search for Last Occurrence:
    • Perform another binary search to find the last occurrence.
    • If nums[mid] matches target, continue searching right.
  3. Return Indices: If target is found, return [first, last], else return [-1, -1].

Time & Space Complexity:

  • Time Complexity: O(log n), since we perform two binary searches.
  • Space Complexity: O(1), as no extra space is used.

Java Implementation:

public class FirstAndLastPosition {
    /**
     * Finds the first and last index of the target in a sorted array.
     * @param nums sorted input array
     * @param target value to search for
     * @return array containing first and last index of target
     * 
     * Time Complexity: O(log n) - Binary search approach.
     * Space Complexity: O(1) - No extra space used.
     */
    public static int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        result[0] = findBound(nums, target, true);
        if (result[0] != -1) {
            result[1] = findBound(nums, target, false);
        }
        return result;
    }
    
    private static int findBound(int[] nums, int target, boolean isFirst) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                if (isFirst) {
                    if (mid == left || nums[mid - 1] != target) return mid;
                    right = mid - 1;
                } else {
                    if (mid == right || nums[mid + 1] != target) return mid;
                    left = mid + 1;
                }
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        int[] input = {5,7,7,8,8,10};
        int target = 8;
        int[] output = searchRange(input, target);
        System.out.println("Output: [" + output[0] + ", " + output[1] + "]");
    }
}

Example:

Input:

nums = [5,7,7,8,8,10], target = 8

Output:

[3, 4]

Edge Cases Considered:

  • Target occurs once → Should return correct index twice.
  • Target is at the start or end → Binary search should work correctly.
  • Target is not in the array → Should return [-1, -1].
  • Empty array → Should return [-1, -1].

Leave a Comment