查找差距相邻数字的有序范围 [英] Finding a gap in an ordered range of adjacent numbers

查看:117
本文介绍了查找差距相邻数字的有序范围的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

这是由史蒂芬Skiena的算法设计手册第2版,第143页。

This is a homework exercise from Steven Skiena's "The algorithm design manual" 2nd edition, p 143.

假设你被赋予不同的整数排序序列 {A1,A2,...一个} ,从 1 M ,其中 N'LT;米。举一个 O(LGN)算法来找到一个整数< = M 不是present在 A 。对于完全学分制,找到最小的这样的整数。

Suppose that you are given a sorted sequence of distinct integers {A1,A2,...An}, drawn from 1 to m where n < m. Give an O(lgN) algorithm to find an integer <= m that is not present in A. For full credit, find the smallest such integer.

有一个排序的序列,而 O(LGN)都表明二进制搜索算法。我能想到的唯一方法是通过从 1 号通过 M 运行,并为每个号码做一个二进制搜索,看是否存在按顺序 A 。但是,这意味着 O(mlgN),不是真的 O(LGN)

A sorted sequence, and O(lgN) both suggest a binary search algorithm. The only way I could think of is to run through numbers from 1 through m, and for each number do a binary search to see if it exists in sequence A. But that means O(mlgN), not really O(lgN).

推荐答案

有一个小于 A [K] 失踪,当且仅当

There is an integer less than A[k] missing if and only if

A[k] > k

(使用1基于索引)。

(using 1-based indexing).

因此​​,要找到最小的失踪数字,二进制搜索。先从中间指数 M 。如果 A [M] GT;米,再没有什么比 A [M] 失踪,在左半搜索一些较小的。否则,如果 A [M] ==米,没有比 M 更小的缺失,你搜索右半部分。

So to find the smallest missing number, binary search. Start with the middle index m. If A[m] > m, then there is a number smaller than A[m] missing, search in the left half. Otherwise, if A[m] == m, there is no smaller number than m missing, and you search the right half.

这篇关于查找差距相邻数字的有序范围的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆