LeetCode49|搜索旋转排序数组

示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

import java.util.HashMap;
import java.util.Map;
import java.util.Optional;
import java.util.stream.IntStream;

public class SearchTest {
    public static void main(String[] args) {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        int target = 0;
        int search = search3(nums, target);
        long startTime = System.currentTimeMillis();
        System.out.println("search = " + search);
        long endTime = System.currentTimeMillis();
        long totalTime = endTime - startTime;
        System.out.println("totalTime = " + totalTime + "毫秒");
    }

    public static int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int length = nums.length;
        HashMap<Integer, Integer> hashMap = new HashMap<>(length);
        for (int i = 0; i < length; i++) {
            hashMap.put(i, nums[i]);
        }
        Optional<Map.Entry<Integer, Integer>> entry = hashMap.entrySet().stream().filter(x -> x.getValue() == target).findFirst();
        if (entry.isPresent()) {
            return entry.get().getKey();
        }
        return -1;
    }

    public static int search2(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int length = nums.length;
        int[] newNums = new int[length];
        System.arraycopy(nums, 0, newNums, 0, length);
        int newLength = newNums.length;
        return IntStream.range(0, newLength).filter(i -> newNums[i] == target).findFirst().orElse(-1);
    }

    public static int search3(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        int mid;
        while (start <= end) {
            mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[start] <= nums[mid]) {
                if (target >= nums[start] && target < nums[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else {
                if (target > nums[mid] && target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }
}