说在前面
🎈每天进行一道算法题目练习，今天的题目是“不动点”。
问题描述
给定已经按 升序 排列、由不同整数组成的数组 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，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。
