首页 > 编程语言 > 详细

33. 搜索旋转排序数组

时间:2021-06-12 00:48:53      阅读:15      评论:0      收藏:0      [点我收藏+]
package leetcode;

public class demo_33 {
    public int search(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        while(left<=right) {
            if(target>nums[right]&&target<nums[left]) {
                return -1;
            }
            int mid=(left+right)/2;
            //如果中间值大于最左边的值,则从最左到中间都是递增的
            if(nums[mid]>=nums[left]) {
                if(nums[mid]>=target) {
                    //判断target是否可能在这个递增区间内
                    if(-1==twodivide(nums,left, mid, target)) {
                        left=mid+1;
                    }
                    else {
                        return twodivide(nums,left, mid, target);
                    }
                }
                else {
                    left=mid+1;
                }
            }
            //如果中间值小于最左边的值,则从中间到最右边都是递增的
            else {
                if(nums[mid]<=target) {
                    //判断target是否可能在这个递增区间内
                    if(-1==twodivide(nums,mid,right, target)) {
                        right=mid-1;
                    }
                    else {
                        return twodivide(nums,mid,right, target);
                    }
                }
                else {
                    right=mid-1;
                }
            }
        }
        return -1;
    }
    //二分查找
    public int twodivide(int nums[],int left,int right,int target) {
        int mid;
        while(left<=right) {
            mid=(left+right)/2;
            if(nums[mid]==target) {
                return mid;
            }
            if(nums[mid]>target) {
                right=mid-1;
            }
            if(nums[mid]<target) {
                left=mid+1;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        demo_33 d33=new demo_33();
        int[]nums={3,1};
        System.out.println(d33.search(nums, 1));
    }

}

 

33. 搜索旋转排序数组

原文:https://www.cnblogs.com/Yshun/p/14876416.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!