Index Equals Value

Tags

Index Equals Value

Category

Searching

Difficulty

Hard

Problem Statement

Given a sorted array of distinct integers (which may include negative numbers), find the first index i such that array[i] == i. If no such index exists, return -1.

Intuition

Define f(i) = array[i] - i. Since the array is sorted and contains distinct integers, f(i) is non-decreasing. When array[i] == i, f(i) == 0. We are searching for the first zero in a non-decreasing sequence, which is a classic binary search problem.

Approach

  1. Initialize left = 0, right = length - 1, and result = -1.
  2. While left <= right:
    • Compute mid = (left + right) / 2.
    • If array[mid] == mid, record result = mid and search left for an earlier match (right = mid - 1).
    • If array[mid] < mid, the fixed point must be to the right (left = mid + 1).
    • If array[mid] > mid, the fixed point must be to the left (right = mid - 1).
  3. Return result.

Pseudocode

function indexEqualsValue(array):
    left = 0
    right = length(array) - 1
    result = -1

    while left <= right:
        mid = (left + right) / 2

        if array[mid] == mid:
            result = mid
            right = mid - 1    // continue searching for earlier match
        else if array[mid] < mid:
            left = mid + 1
        else:
            right = mid - 1

    return result

Time & Space Complexity

  • Time: O(log n) — standard binary search with at most log n iterations.
  • Space: O(1) — only a few integer variables.

Key Insights

  • The distinct and sorted constraints are critical. With distinct integers in a sorted array, if array[i] > i, then for all j > i, array[j] >= array[i] + (j - i) > i + (j - i) = j, so no fixed point exists to the right of an overshoot. Similar reasoning applies to the left for undershoots.
  • Without distinct values, the binary search property breaks, and a different approach is needed.
  • The function f(i) = array[i] - i being non-decreasing is the formal justification for binary search correctness.
  • We continue searching left after finding a match to ensure we return the first (smallest index) fixed point.

Edge Cases

  • Empty array: return -1.
  • All negative values: no index can match (indices are non-negative, but small indices may match if values are also small).
  • Fixed point at index 0: found immediately if array[0] == 0.
  • Fixed point at the last index only: binary search still finds it.
  • No fixed point exists: every check leads to narrowing until left > right, returning -1.
  • Single element array: check if array[0] == 0.

Linked mentions