Implementing binary_search_rightmost in PL/SQL

Problem Definition

Given:

• A sorted array of numbers in ascending order
• A target value t

We want to:

• Return the position of the rightmost element equal to t
• Return 0 if the value is not found, if an exact match is required
• Return the position where the value should be inserted is an exact match is not required

Example

Array: 1,1,2,2,2,3,4,4,4,4,5,6,8 Searching for 4 should return the position 10 (the rightmost, or last 4 in the array).

Why Rightmost Is Non-Trivial

A standard binary search returns the position of an occurrence of the target. But when duplicates exist, we must modify the algorith to:

• Continue narrowing the search interval even after a match
• Preserve the invariant that the target may still exist to the right

This requires a slightly different loop condition than the textbook "stop when equal."

Core Algorithm

The key invariant maintained during the loop:

• The target value, if present, lies within the half-open interval [l ,r]

Where l = left bound of search, r = right bound.

  FUNCTION binary_search_rightmost_array(
    p_target      IN NUMBER,
    p_array       IN t_number_array,
    p_exact_match IN BOOLEAN DEFAULT TRUE
  ) RETURN NUMBER
  IS 
    l PLS_INTEGER; -- Left bound of array to search
    r PLS_INTEGER; -- Right bound of array to search
    n PLS_INTEGER; -- For VARRAY count = last element of array
    t PLS_INTEGER; -- Search target value
    m PLS_INTEGER; -- Mid position of range [l,r]
    p PLS_INTEGER; -- Position of target
    v_debug_module applog.program_name%TYPE := 'UTIL_NUMERIC.BINARY_SEARCH_RIGHTMOST_ARRAY';
    v_debug_msg applog.message%TYPE;
    v_debug_mode VARCHAR2(1) := 'X';
    e_null_value EXCEPTION;
    e_unsorted_array EXCEPTION;
  BEGIN
    IF array_contains_null(p_array) THEN 
      RAISE e_null_value;
    END IF;
    
    IF NOT is_sorted_array(p_array) THEN 
      RAISE e_unsorted_array;
    END IF;
    
    t := p_target;
    n := p_array.LAST;
    l := 1;
    r := n;
    p := 0;
                            
    -- Find position of target t in array
    WHILE l < r LOOP
      m := l + floor((r -l) / 2);
      IF p_array(m) > t THEN 
        r := m;
      ELSE
        l := m+1;
      END IF;
    END LOOP;
              

At the loop exit:

• l points to the first element greater than the target.
• Therefore the rightmost occurrence of the target is at l - 1

Resolution Logic

    IF n > 0 AND p_array(n) = p_target THEN 
      p := n; -- target found at last position of array
    ELSIF l > 1 AND p_array(l-1) = p_target THEN 
      p := l - 1; --target found at 1 position before last left bound searched is the rightmost target
    ELSE 
      IF p_exact_match THEN 
        p := 0; -- target not found, exact match required
      ELSE 
        p := l; -- insertion point for missing value is at last leftmost bound searched
      END IF;
    END IF;
    RETURN p;  
              

This ensures:

• Correct rightmost match, when target = last value in array
• Deterministic insertion behaviour where target not found
• Proper termination of loop - No infinite loops!

Why This Works

The loop maintains [l ,r] as the region where the target may exist.
Each iteration reduces the interval.

• If a(m) > target the target must lie in [l, m]
• Otherwise, it must lie in [m+1, r]

This guarantees:

Strict interval shrinkage
• Termination of loop
• No boundary oscillation

Edge Cases Handled

• Empty arrays
• Single element arrays
• All array values same
• Target rightmost at last position in array
• Target < minimum value in array
• Target > maximum value in array

Additional Validation:

• Arrays must be pre-sorted into ascending order
• NULL values are not allowed

Complexity

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

Even with 32767 elements (the VARRAY limit) binary search performs at most 15 iterations.

Why Not Just Use SQL?

For table-based data, SQL is superior. In most production systems, if the data resides in database tables, SQL is the correct tool for filtering, ranking, and aggregation. Oracle's optimizer, indexing mechanisms, and analytic functions are highly efficient.

  SELECT MAX(pos)
  FROM (
    SELECT sal,
            ROW_NUMBER() OVER (ORDER BY sal) AS pos
    FROM emp
  )
  WHERE sal = :target;
              

However, the UTIL_NUMERIC package operates on:

• In-memory PL/SQL collections
• Deterministic numeric utilities (given same input, same output)
• Reusable library components

The goal is algorithmic correctness, and structural clarity.

When Would You Use binary_search_* Instead of SQL?

There are cases where using the PL/SQL binary_search_* functions are appropriate.

• When operating on in-memory PL/SQL collections (e.g. VARRAY or nested tables).
• When deterministic behaviour is required independent of SQL execution plans.
• When working inside libraries that operate on arrays rather than tables.
• When insertion points, predecessor/successor logic, or rank semantics are required as part of an algorithm.
• When building reusable components that must not depend on table structures.

In these situations, a correctly implemented binary search provides predictable O(log n) behaviour, and clean insertion semantics without requiring expensive context switches between SQL and PL/SQL.