数据结构与算法学习(五)——神奇的二分法

二分法,以优秀的复杂(log_2N)度成功的将顺序查找抛在后面,成为我们最常用的算法。

在我们平常的认知里,二分法只能用于解决有序的数据问题,但对于求解内容的不同,它也可以用于无数的数据中,下面就有序数据和无序数据的相关问题进行总结。

1. 二分法解决有序问题

1.1 查找某个数

1.2 大于等于某数最左侧的位置

2. 二分法解决无序问题

2.1 局部最小值问题

首先来解释一下什么是局部最小值:

  • 如果这个数在0位置:这个数小于1位置上的数;
  • 如果这个数在N位置:这个数小于N-1位置上的数;
  • 如果这个数在其他位置:这个数小于前一个位置上的数,还小于后一位位置上的数。

如果在一个无序数组中,相邻两数不相等,则从0 ~ (N-1)上存在局部最小值

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容