递归与分治 | 4：寻找 a[i] = i 的不动点

向右看齐 2023-07-10 15:58 46阅读 0赞

> **问题**：设n个不同的整数排好序后存于T\[1：n\]中。若存在下标i，1<=i<=n,使得T\[i\]=i,设计一个有效算法找到这个下标。要求算法在最坏情况下的计算时间为O(logn).

暴力扫描的算法时间复杂度时O(n)，要达到 O(logn) 需要用到分治的思想。

--------------------

既然已经给出了排好序的序列，我们假设是**增序的**（降序同理）。由于下标以1为单位增长的，而数组对应的值是以 >=1 的单位增长的，所以，对于一个不动点 a\[j\] = j处，其左端必有 a\[j\] <= j、右端必有 a\[j\] >= j。

我们可以每次找到区间的中点mid：

1.  如果a\[mid\] = mid 那么恰好找到（递归终点）
2.  如果a\[mid\] > mid 那么在mid左边的区间找（递归调用）
3.  如果a\[mid\] < mid 那么在mid右边的区间找（递归调用）

--------------------

代码如下：

/* 一个增序不重复序列a，寻找其[l, r]内满足 a[i] = i 的点(一定存在)的下标i
     * 时间复杂度为O(log n) */
    int FindFixedPoint(int a[], int l, int r) {
        int mid = (l + r) / 2;
        if (a[mid] == mid)  //递归的终点，找到了！
            return mid;
        else if (a[mid] > mid)
            return FindFixedPoint(a, l, mid - 1);  //向左寻找
        else
            return FindFixedPoint(a, mid + 1, r);  //向右寻找
    }

--------------------

# end  #

欢迎关注个人公众号**“** **鸡翅编程 ”**，这里是认真且乖巧的码农一枚。

*---- 做最乖巧的博客er，做最扎实的程序员 ----*

旨在用心写好每一篇文章，平常会把笔记汇总成推送更新~

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200111020715220.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw==,size_16,color_FFFFFF,t_70