【Hot100】LeetCode—33. 搜索旋转排序数组

• 原题链接：33. 搜索旋转排序数组

1- 思路

二分

① 左区间二分、② 寻找目标值所处区间、③ 二分目标值

• ① 左区间二分 ——> 找到最后一个比 nums[0] 大的元素，也就是前半段
  • 即 nums[mid] >= nums[0]
• ② 寻找目标值所在区间
  • if( target >= nums[0]) ——> left = 0;
  • else{ left = left +1; right = nums.length-1;}
• ② 左区间二分，对比值为 target

2- 实现

⭐33. 搜索旋转排序数组——题解思路

class Solution {
    public int search(int[] nums, int target) {
        // 左区间二分
        int left = 0 ;
        int right = nums.length-1;
        while(left<right){
            int mid = left + (right - left) / 2 +1;
            if(nums[mid] >= nums[0]){
                left = mid;
            }else{
                right = mid-1;
            }
        }

        // 区间划分
        if(target >= nums[0]){
            left = 0;
        }else{
            left = left+1;
            right = nums.length-1;
        }

        // 二分目标值
        while(left<right){
            int mid = (left+right+1)/2;
            if(nums[mid] <= target){
                left = mid;
            }else{
                right = mid-1;
            }
        }
        return nums[right] == target? right:-1;
    }
}

3- ACM 实现

public class search {


    public static int binarySearch(int[] nums,int target){
        // 1. 根据 nums[0] 二分
        // 找到区间分界，也就是找到最后一个比 nums[0] 大的元素
        int left = 0 ;
        int right = nums.length-1;
        while (left<right){
            int mid = left + (right-left) /2 +1;
            if(nums[mid]>=nums[0]){
                left = mid;
            }else{
                right = mid-1;
            }
        }

        // 2. 判断区间
        if(nums[0] <= target ) left = 0;
        else {
            left = left+1;
            right = nums.length-1;
        }


        // 3. 二分 target
        while (left<right){
            int mid = (left+right)/2+1;
            if(nums[mid] <= target){
                left = mid;
            }else{
                right = mid-1;
            }
        }
        return target == nums[right] ? right:-1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        input = input.replace("[","").replace("]","");
        String[] parts = input.split(",");
        int[] nums = new int[parts.length];
        for(int i = 0 ; i < nums.length; i++){
            nums[i] = Integer.parseInt(parts[i]);
        }
        System.out.println("输入target");
        int target = sc.nextInt();
        System.out.println("结果是"+binarySearch(nums,target));
    }
}