# LeetCode 1064: Fixed Point

## Problem Restatement

We are given a sorted integer array `arr` with distinct elements.

A fixed point is an index `i` where `arr[i] == i`.

Return the smallest fixed point, or `-1` if none exists.

The official constraints state that `1 <= arr.length <= 10^4`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Sorted array `arr` with distinct integers |
| Output | Smallest index `i` where `arr[i] == i`, or `-1` |

Function shape:

```python
def fixedPoint(arr: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
arr = [-10, -5, 0, 3, 7]
```

`arr[3] = 3`. Fixed point at index 3.

Answer: `3`.

Example 2:

```python
arr = [0, 2, 5, 8, 17]
```

`arr[0] = 0`. Fixed point at index 0.

Answer: `0`.

## Key Insight

Since the array is sorted and has distinct elements, `arr[i] - i` is strictly increasing.

A fixed point exists where `arr[i] - i == 0`.

Binary search on `arr[i] - i`: find the leftmost index where this is zero.

## Edge Cases

- Check the smallest and largest valid search values; off-by-one errors usually appear at the boundaries.
- Decide whether the predicate is looking for the first true value, the last true value, or an exact match.
- When the target is absent, the loop should still terminate and return the problem-specific failure value.

## Common Pitfalls

- Do not mix inclusive and half-open bounds inside the same loop.
- Make sure each branch strictly reduces the search interval.

## Implementation

```python
class Solution:
    def fixedPoint(self, arr: list[int]) -> int:
        lo, hi = 0, len(arr) - 1
        result = -1

        while lo <= hi:
            mid = (lo + hi) // 2
            if arr[mid] == mid:
                result = mid
                hi = mid - 1
            elif arr[mid] < mid:
                lo = mid + 1
            else:
                hi = mid - 1

        return result
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.fixedPoint([-10,-5,0,3,7]) == 3
    assert s.fixedPoint([0,2,5,8,17]) == 0
    assert s.fixedPoint([-10,-5,3,4,7,9]) == -1

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `[-10,-5,0,3,7]` | `3` | `arr[3]=3` |
| `[0,2,5,8,17]` | `0` | `arr[0]=0` |
| No fixed point | `-1` | No `i` with `arr[i]=i` |