【二分查找】面试题 08.03. 魔术索引

这篇具有很好参考价值的文章主要介绍了【二分查找】面试题 08.03. 魔术索引。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

面试题 08.03. 魔术索引

解题思路

【二分查找】面试题 08.03. 魔术索引,Algorithm,# Leetcode,java,算法,面试文章来源地址https://www.toymoban.com/news/detail-544065.html

  • 改写递归二分查找的思路
  • 首先查找mid的值是不是mid 如果是 由于有多个解,那么递归搜索左半边的空间
  • 然后如果没找到,首先搜索左半边的空间,然后搜索右半边的空间
class Solution {

    public int res = -1;

    private void search(int[] nums,int low,int high){
        if(low > high){
            return;
        }

        int mid  = low + (high  - low) / 2;

        // 如果找到 直接搜索左半边的空间
        if(nums[mid] == mid){
            res = mid;// 保存一下结果
            search(nums,low,mid - 1);// 搜索左半边的空间
        }
        else{
            // 如果没有找到  先搜索左半边 然后搜索右半边
            search(nums,low,mid - 1);
            if(res == -1 || res > high){
                // 搜索右半边
                search(nums,mid + 1,high);
            }
        }

    }

    // 递归二分查找
    public int findMagicIndex(int[] nums) {
       search(nums,0,nums.length - 1);
       return res;
    }
}

到了这里,关于【二分查找】面试题 08.03. 魔术索引的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode刷题笔记-704.二分查找

     我们定义target在一个左右都是关闭的区间,[left,right] while(left = right) 这里使用= 因为left == right 是有意义的 int mid = left + ((right - left) / 2) 这么写是为了防止溢出 常用操作 当nums[mid] target 将right = mid - 1因为target 不可能在mid处取到 当nums[mid] target 将left = mid + 1

    2024年02月11日
    浏览(55)
  • 每日一题(LeetCode)----二分查找(一)

    给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 示例 2: 示例 3: 提示: 1 = nums.length = 104 -104 = nums[i] = 104 nums 为 无重复元素 的 升序 排列数

    2024年02月08日
    浏览(50)
  • Leetcode 704.二分查找、27.移除元素

    暴力循环: 自己的思路 从左往右,遍历每个元素。 检查当前元素是否满足要求。 若满足要求则返回当前元素的下标。 时间复杂度:O(n); 空间复杂度:O(n); 二分查找: 题目给定的是一个升序的数组,即有序数组! 那么二分的前提是有序(或者具有某种特殊的性质!)。

    2024年02月17日
    浏览(51)
  • LeetCode-74. 搜索二维矩阵【数组 二分查找 矩阵】

    给你一个满足下述两条属性的 m x n 整数矩阵: 每行中的整数从左到右按非严格递增顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false 。 示例 1: 输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]],

    2024年04月14日
    浏览(47)
  • 代码随想录 LeetCode数组篇 二分查找

    # (简单)704. 二分查找 题目链接 代码随想录 - 二分查找思路 二分查找,思路很简单,但是在while循环left和right的比较是写=还是,还有right=mid还是right=mid-1容易混淆 需要想清楚对区间的定义,是[left,right],还是[left,right) (版本一,左闭右闭版本) (版本二,左闭右开) 题目

    2024年02月02日
    浏览(57)
  • 二分查找两个模板,leetcode35.搜索插入位置

    在有序数列中,查找某个元素是否存在 扩展一下: 在有序数列中(通常是非递减,可以有重复元素),查找第一个满足xx条件的元素 每次搜索区间减半,时间复杂度 O ( l o g n ) O(logn) O ( l o g n ) 1.初始边界为0和n-1,如果你的下标从1开始,那就是1和n,效果一样, 只需要确保初始

    2024年02月20日
    浏览(40)
  • 【二分查找】【双指针】LeetCode:2565最少得分子序列

    【动态规划】【广度优先】LeetCode2258:逃离火灾 二分查找算法合集 有序向量的 二分查找 ,初始化完成后,向量不会修改。 双指针 : 用于计算子字符串是s的字符串的子系列。 给你两个字符串 s 和 t 。 你可以从字符串 t 中删除任意数目的字符。 如果没有从字符串 t 中删除字

    2024年02月05日
    浏览(58)
  • Day1 LeetCode 704.二分查找 27.移除元素

    704.二分查找 题目链接: 力扣 文章讲解: 代码随想录 视频讲解: 手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找_哔哩哔哩_bilibili 看完随想录之后的想法 两种情况1.左闭右闭  [ ]  2.左闭右开 [ )  当定义时为左闭右闭时,while中if的条件可以

    2024年02月15日
    浏览(41)
  • 代码随想录第一天 | LeetCode704.二分查找,LeetCode 27.移除元素

    数组理论基础要点: 数组也是数据结构的一种, 是存放在连续内存空间上的相同类型数据的集合。 数组注意点: 数组下标都是从0开始的。 数组内存空间的地址是连续的。 因为上述两点, 数组的在内存空间的地址是连续的,所以我们在删除或者增添元素的时候,就难免要

    2024年02月08日
    浏览(50)
  • [二分查找]LeetCode2040:两个有序数组的第 K 小乘积

    二分查找算法合集 给你两个 从小到大排好序 且下标从 0 开始的整数数组 nums1 和 nums2 以及一个整数 k ,请你返回第 k (从 1 开始编号)小的 nums1[i] * nums2[j] 的乘积,其中 0 = i nums1.length 且 0 = j nums2.length 。 示例 1: 输入:nums1 = [2,5], nums2 = [3,4], k = 2 输出:8 解释:第 2 小的乘

    2024年02月04日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包