【算法】递归算法 ② ( 使用递归实现二分法

文章目录

一、使用递归实现二分法
- 1、递归三要素分析
- 2、代码示例
二、if else 编码优化

一、使用递归实现二分法

https://leetcode.cn/problems/binary-search/

典型的二分查找题目 : 从一个有序数组中查找某个目标值 , 返回该目标元素在数组中的索引值 , 如果数组中没有该目标值 , 则返回 -1 ;

如 : 从 [1 , 2 , 4 , 5 , 6] 中查找目标值 2 , 返回 2 对应的数组元素索引为 1 ; 如果从上述数组中查找 3 , 数组中没有该元素 , 则返回 -1 ;

使用递归实现二分法 , 目的是不断缩小二分区间 , 每次进行递归的操作是取一个中点 , 进行比较 , 确定向左收缩还是向右收缩 ;

二分法的时间复杂度是

log(n)

, 递归的深度也是

O(log n)

, 基本不会出现栈溢出 ;

如果递归深度是

O(n)

则出现栈溢出风险较大 ;

1、递归三要素分析

分析使用递归实现二分法的递归三要素 :

递归定义 : 分析函数的参数 , 返回值 , 以及代表的含义 ;
- 参数分析 : 二分法需要接收四个参数 ,
  - 数组集合 ,
  - 查找元素的区间范围 , 起始索引和终止索引 , 这是 2 个参数 ,
  - 进行对比的目标值
- 返回值分析 : 返回值就是获取的目标值在数组中的索引 ;
递归拆解 : 分析每次递归需要执行的操作 , 就是递归函数的具体内容 ;
- 缩小查找规模 : 二分法的核心操作就是不断缩小查找元素的区间范围 , 判断区间中心元素与目标值的大小关系 - 如果中心元素 = 目标值 , 直接返回该索引值 ; - 如果中心元素 < 目标值 , 则需要去该查找区间的右侧继续查找 ; - 如果中心元素 > 目标值 , 则需要去该查找区间的左侧继续查找 ;
递归出口 : 每个递归都需要一个停止条件 , 递归不断循环会造成栈内存溢出 ;
- 没有找到 : 如果查找的区间范围出现起始位置 > 结束位置 , 说明没有找到该元素 , 直接返回 -1 ;
- 成功找到 : 如果查找过程中出现中心元素 = 目标值 , 直接返回该索引值 ;

2、代码示例

代码语言：javascript复制

class Solution {
    public int search(int[] nums, int target) {
        return binarySearch(nums, 0, nums.length - 1, target);
    }
	
	// 1. 递归定义 : 分析函数的 参数 , 返回值 , 以及代表的含义
	// 二分法需要接收四个参数 : 
	// 数组集合
	// 查找元素的区间范围 , 起始索引 和 终止索引 , 这是 2 个参数
	// 进行对比的目标值
	// 返回值 : 进行对比的目标值
    private int binarySearch(int[] nums, int start, int end, int target) {
        // 3. 递归出口 : 
        // 没有找到 : 如果查找的区间范围出现 起始位置 > 结束位置 , 
        //           说明没有找到该元素 , 直接返回 -1 ;
        if (start > end) {
            return -1;
        }
		// 成功找到 : 如果查找过程中出现 中心元素 = 目标值 , 直接返回该索引值
        int mid = (start   end) / 2;
        if(nums[mid] == target) {
            return mid;
        }

		// 2. 递归拆解 : 分析每次 递归需要执行的操作 , 就是递归函数的具体内容
		// 缩小查找规模 : 二分法的核心操作就是不断缩小 查找元素的区间范围 ,  
		//               判断区间中心元素 与 目标值的 大小关系 
		// 如果 中心元素 < 目标值 , 则需要去 该查找区间的 右侧继续查找
        if(nums[mid] < target) {
            return binarySearch(nums, mid   1, end, target);
        }
        // 如果 中心元素 > 目标值 , 则需要去 该查找区间的 左侧继续查找
        return binarySearch(nums, start, mid - 1, target);
    }
}

二、if else 编码优化

在代码中使用 if 进行判定时 , 推荐少用 else 语句 ;

使用了 else 关键字有以下坏处 :

代码不美观 : 一旦使用了 else , 则在 else 中的所有语句都会缩进一行 , 如果使用层数过多 , 会有多层缩进 ;
可读性差 : 在代码中 , 使用的 else 越多 , 代码的可读性越差 ;

如果要使用 if else 语句 , 推荐将这个逻辑单独封装到一个函数中 , 在函数内部使用 if return 来替代 if else ;

下面的代码的判定方式判定 nums[mid] 和 target 的大小 , 有三种情况 :

等于
小于
大于

可以使用 if else 语句进行编码 , 但是此处使用了 if return 的形式 , 代码要更加简洁 , 易读 ;

代码语言：javascript复制

        if(nums[mid] == target) {
            return mid;
        }
        if(nums[mid] < target) {
            return binarySearch(nums, mid   1, end, target);
        }
        return binarySearch(nums, start, mid - 1, target);

编码递归数组算法索引

0 人点赞

【算法】递归算法 ② ( 使用递归实现二分法 | if else 编码优化 )

文章目录

一、使用递归实现二分法

1、递归三要素分析

2、代码示例

二、if else 编码优化