z******t
发帖数: 59 | 1 如果要求在一个排序的数组里找出一个数字，则可以考虑采用二分查找法。数组可能是
完全排序的，也可能是部分排序，比如前半部分是递增排序，后半部分是递减排序。
先后写了三篇博客讨论这种类型的题目，供参考：
(1) Turning Number in an Array
Turning number is the maximum number in an array which increases and then
decreases. This kind of array is also named unimodal array. Please write a
function which gets the index of the turning number in such an array.
For example, the turning number in array {1, 2, 3, 4, 5, 10, 9, 8, 7, 6} is
10, so its index 5 is the expected output.
http://codercareer.blogspot.com/2011/11/no-22-turning-number-in
(2) Search in a Rotation of an Array
When some elements at the beginning of an array are moved to the end, it
gets a rotation of the original array. Please implement a function to search
a number in a rotation of an increasingly sorted array. Assume there are no
duplicated numbers in the array.
For example, array {3, 4, 5, 1, 2} is a rotation of array {1, 2, 3, 4, 5}.
If the target number to be searched is 4, the index of the number 4 in the
rotation 1 should be returned. If the target number to be searched is 6, -1
should be returned because the number does not exist in the rotated array.
http://codercareer.blogspot.com/2013/03/no-47-search-in-rotatio
(3) Integer Identical to Index
Integers in an array are unique and increasingly sorted. Please write a
function/method to find an integer from the array who equals its index. For
example, in the array {-3, -1, 1, 3, 5}, the number 3 equals its index 3.
http://codercareer.blogspot.com/2014/10/no-57-integer-identical | c***z
发帖数: 6348 | |
|
