搜索旋转数组

Given a sorted array of n integers that has been rotated an unknown number of times, write code to find an element in the array. You may assume that the array was originally sorted in increasing order. If there are more than one target elements in the array, return the smallest index.

Example1:

 Input: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
 Output: 8 (the index of 5 in the array)

Example2:

 Input: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
 Output: -1 (not found)

Note:

1. 1 <= arr.length <= 1000000

/**
 * 使用 Java Stream 查找旋转数组中的某个元素。
 * 思路：
 * 1. 利用流操作来查找目标元素的索引。
 * 2. 使用IntStream.range来生成索引范围并在流中查找目标值。
 */
import java.util.stream.IntStream;

public class SolutionStream {
    public int search(int[] nums, int target) {
        return IntStream.range(0, nums.length)
                .filter(i -> nums[i] == target)
                .findFirst()
                .orElse(-1);
    }
}

这道题涉及到在一个部分旋转的有序数组中寻找一个特定的元素。解题关键在于如何有效利用数组的部分有序特性来减少搜索范围。首先，通过比较数组首尾元素实现区间的切分。算法首先检查当前左边界元素是否是目标元素，如果是则直接返回。接着，计算中间索引，并检查中间元素是否为目标，如果是则更新右边界为中间，以缩小搜索范围并可能找到最小索引。然后，算法检查左半部分是否有序（即左端元素小于等于右端元素）。根据有序部分的情况，决定是向左还是向右继续搜索，从而不断缩小查找范围。通过这种方式，算法能够在对数时间内找到目标元素或确定其不存在。

O(log n) in best case, O(n) in worst case

O(1)