Java实现旋转排序数组中查找元素

x33g5p2x  于2022-09-14 转载在 Java  
字(1.3k)|赞(0)|评价(0)|浏览(253)

旋转排序数组搜索

假设一个按升序排序的数组在某个未知的枢轴处旋转。 (即,[1, 4, 6, 8, 11, 13, 15] 可能变为 [8, 11, 13, 15, 1, 4, 6])。

您将获得要搜索的目标值。 如果在数组中找到返回它的索引,否则返回-1。

您可以假设数组中不存在重复项。 你的算法的运行时复杂度必须在 O(log n) 的数量级。

示例 1:

Input: nums = [8, 11, 13, 15, 1, 4, 6], target = 1
Output: 4

示例 2:

Input: nums = [1, 4, 6, 8, 11, 13, 15], target = 3
Output: -1

Java 中的旋转排序数组搜索解决方案

虽然整个数组不是从左到右排序的,但是枢轴左侧和枢轴右侧的子数组仍然会被排序。 我们可以利用这一事实并应用二分查找以 O(log(n)) 时间复杂度在数组中查找元素。 为了清楚起见,以下是带有注释的问题的解决方案:

import java.util.Scanner;

class RotatedSortedArraySearch {
    private static int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;

        while(start <= end) {
            int mid = (start + end)/2;

            if(target == nums[mid]) {
                return mid;
            }

            if(nums[start] <= nums[mid]) { // left array is sorted
                if(target >= nums[start] && target < nums[mid]) { // target lies between start and mid index
                    end = mid-1;
                } else {
                    start = mid+1;
                }
            } else { // right array is sorted
                if(target > nums[mid] && target <= nums[end]) { // target lies between mid and end index
                    start = mid+1;
                } else {
                    end = mid-1;
                }
            }
        }

        return -1;
    }


    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i++) {
          nums[i] = keyboard.nextInt(); 
        }
        int target = keyboard.nextInt();
        keyboard.close();

        System.out.printf("Search(%d) = %d%n", target, search(nums, target));
    }
}
# Output
$ javac RotatedSortedArraySearch.java
$ java RotatedSortedArraySearch
7
8 11 13 15 1 4 6
1
Search(1) = 4

相关文章

微信公众号

最新文章

更多