萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

力扣第33题-搜索旋转排序数组

发表于 2023-03-17 | 分类于 力扣刷题 | 0 | 阅读次数 6

题目
题目链接

题解

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

    /**
     * 非排序数组二分查找
     * @param nums 数组
     * @param target 目标
     * @param left 左起点
     * @param right 右起点
     * @return 目标下标,-1为没找到
     */
    private int specialBinarySearch(int[] nums, int target, int left, int right) {
        if (nums == null || nums.length < 1 || left < 0 || right < 0 || left > right || left > nums.length - 1 || right > nums.length - 1) {
            return -1;
        }
        if (right == left && nums[right] == target) {
            return right;
        }
        for (int l = left, r = right, mid = (l + r) / 2; l <= r;) {
            // 判断原数组0下标在mid左侧还是右侧
            if (nums[mid] < nums[r]) {
                // 在mid左侧或者命中mid
                // target与nums[mid]比较
                if (target > nums[mid]) {
                    // nums[0] < target < 原nums[0] || nums[mid] < taget < nums[len - 1]
                    // 查找右侧
                    int index = binarySearch(nums, target, mid, r);
                    if (index != -1) {
                        return index;
                    } else {
                        // nums[mid] < taget < nums[len - 1] 不成立,那只可能是 nums[0] < taget < 原nums[0],重新选举mid
                        // 下一步查找左侧
                        r = mid;
                        mid = (l + r) / 2;
                        if (l + 1 >= r) {
                            if (target == nums[l]) {
                                return l;
                            } else if (target == nums[r]) {
                                return r;
                            } else {
                                return -1;
                            }
                        }
                    }
                } else if (target < nums[mid]) {
                    // 原nums[0] < target < mid,重新选举mid
                    // 下一步查找左侧
                    r = mid;
                    mid = (l + r) / 2;
                    if (l + 1 >= r) {
                        if (target == nums[l]) {
                            return l;
                        } else if (target == nums[r]) {
                            return r;
                        } else {
                            return -1;
                        }
                    }
                } else {
                    return mid;
                }
            } else {
                // 在mid右侧
                // target与nums[mid]比较
                if (target < nums[mid]) {
                    // nums[0] < target < nums[mid] || 原nums[0] < target < nums[len - 1]
                    int index = binarySearch(nums, target, l, mid);
                    if (index != -1) {
                        return index;
                    } else {
                        // nums[0] < target < nums[mid]不成立,确定目标在:原nums[0] < target < nums[len - 1]
                        // 下一步查找右侧
                        l = mid;
                        mid = (l + r) / 2;
                        if (l + 1 >= r) {
                            if (target == nums[l]) {
                                return l;
                            } else if (target == nums[r]) {
                                return r;
                            } else {
                                return -1;
                            }
                        }
                    }
                } else if (target > nums[mid]) {
                    // nums[mid] < target < 原nums[0]
                    // 下一步查找右侧
                    l = mid;
                    mid = (l + r) / 2;
                    if (l + 1 >= r) {
                        if (target == nums[l]) {
                            return l;
                        } else if (target == nums[r]) {
                            return r;
                        } else {
                            return -1;
                        }
                    }
                } else {
                    return mid;
                }
            }
        }
        return -1;
    }

    /**
     * 普通二分查找
     * @param nums 数组
     * @param target 目标
     * @param left 左起点
     * @param right 右起点
     * @return 目标下标,-1为没找到
     */
    private int binarySearch(int[] nums, int target, int left, int right) {
        if (nums == null || nums.length < 1 || left < 0 || right < 0 || left > right || left > nums.length - 1 || right > nums.length - 1) {
            return -1;
        }
        if (right == left && nums[right] == target) {
            return right;
        }
        for (int l = left, r = right, mid = (l + r) / 2; l <= r;) {
            if (target > nums[mid]) {
                l = mid;
            } else if (target < nums[mid]) {
                r = mid;
            } else {
                return mid;
            }
            mid = (l + r) / 2;
            if (l + 1 >= r) {
                if (nums[l] == target) {
                    return l;
                } else if (nums[r] == target) {
                    return r;
                } else {
                    return -1;
                }
            }
        }
        return -1;
    }
}
# 算法 # 程序设计 # 力扣
力扣第32题-最长有效括号
力扣第34题-在排序数组中查找元素的第一个和最后一个位置
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

83 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持