leetcode33 搜索旋转排序数组

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了leetcode33 搜索旋转排序数组，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1758字，纯文字阅读大概需要3分钟。

内容图文

思路：(好像剑指offer也有这一题)

1.这种题直接搜索肯定会超时。所以考点肯定是二分法。

2.旋转数组有什么特点呢？我个人觉得就是最开头的数，比它小的数字肯定在尾部。

知识点复习

首先要懂二分法基本写法：(我从网上抄的，只强调一点:mid应该用减法来计算，防止溢出)

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; 

    while(left <= right) { 
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; 
        else if (nums[mid] > target)
            right = mid - 1; 
        }
    return -1;
}

然后也没什么了，基本思路都写在注释里了，注意下细节就行（断点：两截序列的交叉）

代码如下：

class Solution {
    public int search(int[] nums, int target) {
        if(nums==null || nums.length==0){
            return -1;
        }
        if(nums.length==1) return target==nums[0]?0:-1;
        return dfs(nums,0,nums.length-1,target);
    }

    private int dfs(int[] nums,int left,int right,int target) {

        if(left > right) {
            return -1;
        }
        int mid = (left+right)/2;
        if(target == nums[mid]) {
            return mid;
        }
        //左半边是升序，断点在右边
        if(nums[mid]>nums[left]) {
            if(target<nums[left]) {
                //只可能去右半边查找
                return dfs(nums,mid+1,right,target);
            }else if(target == nums[left]){
                return left;
            }else if(target>nums[left]){
                //这里不可能等于，之前已经判断了。
                if(target>nums[mid]) {
                    //去右半边查找
                    return dfs(nums,mid+1,right,target);
                }else {
                    return dfs(nums,left,mid-1,target);
                }
            }
        } else if(nums[mid]<nums[left]) {
            // 断点在左边
            if(target>nums[left]) {
                //只可能去左半边查找
                return dfs(nums,left,mid-1,target);
            }else if(target == nums[left]){
                return left;
            }else if(target<nums[left]){
                if(target>nums[mid]) {
                    // 右边
                    return dfs(nums,mid+1,right,target);
                }else {
                    // 左边
                    return dfs(nums,left,mid-1,target);
                }
            }
        }else if(nums[mid] == nums[left]){
            //mid == left
            if(nums[left] == target) return left;
            if(nums[right] == target) return right;
        }
        return -1;
    }
}

 

内容总结

以上是互联网集市为您收集整理的leetcode33 搜索旋转排序数组全部内容，希望文章能够帮你解决leetcode33 搜索旋转排序数组所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---