不动点

说在前面

🎈每天进行一道算法题目练习，今天的题目是“不动点”。

问题描述

给定已经按 升序 排列、由不同整数组成的数组 arr，返回满足 arr[i] == i 的最小索引 i。如果不存在这样的 i，返回 -1。

示例 1：

输入：arr = [-10,-5,0,3,7]
输出：3
解释：对于给定的数组，arr[0] = -10，arr[1] = -5，arr[2] = 0，arr[3] = 3，因此输出为 3 。

示例 2：

输入：arr = [0,2,5,8,17]
输出：0
解释：arr[0] = 0，因此输出为 0 。

示例 3：

输入：arr = [-10,-5,3,4,7,9]
输出：-1
解释：不存在这样的 i 满足 arr[i] = i，因此输出为 -1 。

提示：

1 <= arr.length < 10^4
-10^9 <= arr[i] <= 10^9

思路分析

阅读完题目后，我们可以知道，题目要求是要我们找到不动点，那么什么是不动点呢？题目是这样说的，满足arr[i] == i的最小索引i即是我们要找的不动点。
理解了题目之后，你是不是会觉得这题目就很简单的了，我们可以有以下两种做法。

1、暴力遍历O(n)

我们可以从前往后遍历，遇到第一个arr[i] == i时，此时的i就是题目要求的结果，我们直接return就可以了。

/**
 * @param {number[]} arr
 * @return {number}
 */
var fixedPoint = function(arr) {
    for(let i = 0; i < arr.length; i++) if(arr[i] === i) return i;
    return -1;
};

暴力遍历确实可以找出要求的结果，但是对于此题来说，我们还有更优的解法。

2、二分法O(log(n))

因为题目中说了给出的数组arr是按升序排序的，所以我们可以使用二分法来折半缩小搜索区间。我们只需要维护区间的左右两个端点，当区间中点的数字大于等于中点的下标时，我们需要缩小原来的区间，修改右端点为当前的中点，当区间中点的数字小于中点的下标时，我们也需要缩小原来的区间，修改左端点为当前的中点。

/**
 * @param {number[]} arr
 * @return {number}
 */
var fixedPoint = function(arr) {
    let l=0,r=arr.length-1;
    while(l<r){
        let mid = Math.floor((l+r)/2)
        if(arr[mid]>=mid)
            r=mid
        else
            l=mid+1
    }
    if(arr[l]==l) return l
    else return -1
};

说在后面

🎉这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。