Essential Array Algorithms: Span, Second Largest, Floor, Ceil, and Bitonic Search

1. Span of Array

Problem Statement:
Find the span of an array (the difference between the maximum and minimum elements).

Example:
Input: [3, 4, 7, 10, 1]
Output: 9 (since 10 - 1 = 9)

Approach:

• Initialize max = -∞ and min = +∞.
• Traverse the array once:
  • Update max if the current element is greater than max.
  • Update min if the current element is less than min.
• Return max - min.

Time Complexity: O(n)
Space Complexity: O(1)

2. Second Largest Element

Problem Statement:
Find the second largest element in an array without sorting it.

Example:
Input: [20, 42, 99, 10, 88, 6]
Output: 88

Approach:

• Initialize two variables: max1 (largest) and max2 (second largest).
• Compare the first two elements to set initial values for max1 and max2.
• From the third element onward, iterate:
  • If the element is greater than max1:
    • Set max2 = max1, then max1 = element.
  • Else if the element is greater than max2:
    • Update max2 = element.
• Return max2.

Edge Case: If the array has only 1 element, return -1.

Time Complexity: O(n)
Space Complexity: O(1)

3. Floor and Ceil in a Sorted Array

Problem Statement:
Given a sorted array and a target number x, find:

• Floor: The greatest element less than or equal to x.
• Ceil: The smallest element greater than or equal to x.

Example:
Input: arr = [2, 4, 6, 8, 10], x = 5
Output: floor = 4, ceil = 6

Approach (Binary Search):

• Use binary search to locate x.
• If x is found, both floor and ceil are x.
• If x is not found:
  • When the loop terminates, low points to the next greater element (ceil).
  • high points to the previous smaller element (floor).
• Handle boundary cases where x is less than the minimum or greater than the maximum element.

Time Complexity: O(log n)
Space Complexity: O(1)

Related Problems: Find Insert Position of element in a sorted array

Search Element in a Bitonic Array

Problem Statement:
Given a bitonic array (an array that strictly increases then strictly decreases), find the index of a target element using binary search logic. If the element is not present, return -1.

Example:
Input: arr = [3, 5, 3, 2, 0], target = 0
Output: 4

🔍 Approach Steps

Step 1: Find the Bitonic (Peak) Index

• Use modified binary search:
  • If arr[mid] < arr[mid + 1], the peak is to the right (l = mid + 1).
  • Else, the peak is at or to the left (r = mid).
• The loop terminates when l == r, which is the peak index.

Step 2: Binary Search on the Increasing (Left) Part

• Perform a normal binary search on the subarray from the start up to the peak index. (If arr[m] < target, then l = m + 1).

Step 3: Binary Search on the Decreasing (Right) Part

• If the element is not found in Step 2, perform a reverse binary search on the subarray from the peak index + 1 to the end. (If arr[m] > target, then l = m + 1 because the array is descending).

Time Complexity

Finding peak: O(log n)

Searching both sides: O(log n)

Overall: O(log n)