算法Day05-算法研习指导之二分查找

约定不等于承诺〃 2023-03-03 11:15 18阅读 0赞

### 二分查找 ###

*  基本概念
 *  二分查找框架
 *  寻找一个数
 *  寻找左侧边界
 *  寻找右侧边界
 *  统一二分查找算法
 *   *   *   *   *  基本二分查找算法
                 *  寻找左侧边界的二分查找算法
                 *  寻找右侧边界的二分查找算法
                 *  统一二分查找算法代码实现
 *  二分查找算法总结

# 基本概念 #

*  **二分查找:** 思路很简单,细节很重要
    
     *  给**mid**加**1**还是减**1**
     *  while中是使用 **<=** 还是 **<**
 *  二分查找的场景:
    
     *  **寻找一个数**
     *  **寻找左侧边界**
     *  **寻找右侧边界**

# 二分查找框架 #

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

*  不要出现**else,** 而是将所有情况用**else if**写清楚,这样可以清楚地展现所有细节
 *  计算**mid**时需要防止溢出:
    
     *  使用 l e f t + r i g h t − l e f t 2 left +\\frac\{right - left\}\{2\} left\+2right−left和 l e f t + r i g h t 2 \\frac\{left + right\}\{2\} 2left\+right的结果相同
     *  但是有效防止了**left**和**right**值太大相加导致的溢出问题

# 寻找一个数 #

*  **寻找一个数:** 搜索一个数,如果存在,返回索引,否则返回-1

int binarySearch(int[] nums, int target) { 
    	int left = 0;
    	int right = nums.length -1; // 注意!
    
    	while (left <= right) { 
    		int mid = left + (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;
    }

*  **问题1: 为什么while循环的条件中是 <= , 而不是 < ?**
    
     *  因为初始化**right**的赋值是**nums.length - 1,** 即最后一个元素的索引,而不是**nums.length**
     *  **nums.length - 1**和**nums.length**可能出现在不同功能的二分查找中,区别是:
        
         *  **nums.length - 1**相当于两端都闭区间 **\[left,right\],**
         *  **nums.length**相当于左闭右开区间 **\[left,right)**
         *  因为索引大小为**nums.length**时是越界的
     *  这里使用的是**nums.length - 1,** 相当于两端都闭区间 **\[left,right\].** 这个区间就是每次进行搜索的区间
 *  **问题2: 什么时候应该终止搜索?**
    
     *  找到目标值时就终止搜索,返回索引
        
         *  但是如果没有找到目标值,就需要**while**循环终止,然后返回 **-1**
     *  **while**循环在搜索区间为空的时候应该终止,返回 **-1:**
        
         *  **while(left <= right)** 的终止条件是**left == right + 1,** 写成区间的形式就是 **\[right+1,right\].** 此时区间为空 **,while**循环终止,直接返回 **-1**
         *  **while(left < right)** 的终止条件是**left == right,** 写成区间的形式就是 **\[right,right\].** 此时区间非空,但是**while**循环终止,区间 **\[right,right\]** 被漏掉了,索引**right**没有被搜索到,这时直接返回 **-1**就是错误的
     *  如果一定要使用**while(left < right)** 作为循环终止条件,需要对代码进行优化:
    
        ...
        while (left < right) { 
        }
        return nums[left] == target ? left : -1;
 *  **问题3: 为什么有时是left = mid +1, right = mid -1? 有时是right = mid或者left = mid,没有这些加加减减? 这是什么原因? 怎么判断?**
    
     *  二分查找中要关注**搜索区间**
     *  本算法的搜索区间是两端都闭区间,即 **\[left,right\].** 当索引**mid**不是需要寻找的**target**时
     *  下一步应该是搜索 **\[left,mid-1\]** 或者 **\[mid+1,right\].** 因为**mid**已经搜索过了,所以应该从搜搜区间中去除
 *  **问题4: 这个二分查找算法的缺陷?**
    
     *  这个二分查找算法的局限性: 无法查找边界数
        
         *  有序数组**nums = \[1, 2, 2, 2, 3\], target**为**2.** 如果想得到**target**的左侧边界,即值**1.** 或者想得到**target**的右侧边界,即**3.** 这个二分查找算法是无法处理的
     *  如果使用找到一个**target,** 然后向左或者向右线性搜索可以解决查找边界数的问题,但是这样就难以保证二分查找的对数级的算法复杂度了

# 寻找左侧边界 #

int left_bound(int[] nums, int target) { 
    	if (nums.length == 0) { 
    		return -1;
    	}
    	int left = 0;
    	int right = nums.length;	// 注意!
    
    	while (left < right) { 	// 注意!
    		int mid = left + (right - left) / 2;
    		if (nums[mid] == target) { 
    			right = mid;
    		} else if (nums[mid] < target) { 
    			left = mid + 1;
    		} else if (nums[mid] > target) { 
    			right = mid;	// 注意!
    		}
    	}
    	return left;
    }

*  **问题1: 为什么while是 < 而不是 <= ?**
    
     *  因为初始化时**right = nums.length,** 而不是**nums.length - 1**
     *  因此每次循环的 **\[搜索区间\]** 是 **\[left, right)** 左闭右开
     *  **while (left < right)** 的循环终止条件是 **left == right,** 此时搜索区间为 **\[left, left),** 搜索区间为空,所以可以正确终止
 *  **问题2: 为什么基本二分查找算法的right是nums.length - 1? 搜索左右边界的right要写成nums.length使得搜索区间编程左闭右开呢?**
    
     *  对于搜索左右边界的二分查找算法,通常情况下使用**right**为**nums.length - 1**
     *  如果使用两端都闭的写法反而更简单
 *  **问题3: 为什么没有返回 -1的操作? 如果nums中不存在target这个值,怎么处理?**
    
     *  对于有序数组**nums\[2, 3, 5, 7\], target = 1,** 算法会返回**0,** 表示 **: nums**中小于**1**得元素有**0**个
     *  对于有序数组**nums\[2, 3, 5, 7\], target = 8,** 算法会返回**4,** 表示 **: nums**中小于**8**的元素有**4**个
     *  由此可见,函数的返回值即**left**变量的值的取值区间是闭区间 **\[0, nums.length\].** 增加代码在正确的时候**return -1 :**

while (left < right) { 
    	...
    }
    // target比所有数都大
    if (left == nums.length) { 
    	return -1;
    }
    // 返回左侧边界
    return num[left] == target ? left : -1;

*  **问题4: 为什么left = mid + 1, right = mid? 和基本二分查找算法的不一样?**
    
     *  因为 **\[搜索区间\]** 是 **\[left, right)** 左闭右开区间, 所以当**nums\[mid\]** 被检测之后,下一步的搜索区间应该去掉**mid**分割成的两个区间,即为 **\[left, mid)** 或者 **\[mid + 1, right)**
 *  **问题5: 为什么该算法能够搜索左侧边界?**
    
     *  搜索左侧边界算法的关键在于对于**nums\[mid\] == target**情况的处理:
    
        if (nums[mid] == target) { 
        		right = mid;
        	}
    
     *  找到**target**时,不是立即返回,而是缩小 **\[搜索区间\]** 的上界**right,** 然后在 **\[left, mid)** 中继续搜索,即不断向左收缩,达到锁定左侧边界的目的
 *  **问题6: 为什么返回left而不是right?**
    
     *  返回**left**和返回**right**都是一样的
     *  因为**while**的循环终止条件是**left == right**
 *  **问题7: 可不可以将right初始值设置为nums.length - 1, 也就是继续使用两边都闭的\[搜索区间\]? 这样可以将基本二分查找算法和寻找左侧边界的二分查找算法在某种程度上统一起来?**
    
     *  可以,只要理解 **\[搜索区间\],** 有效避免漏掉元素就可以
        
         *  因为 **\[搜索区间\]** 两端都是闭区间,所以**right**的初始值设置为**nums.length - 1,while**的终止条件应该是**left = right + 1,** 所以**while**中的条件应该使用**while(left <= right)**
        
            int left_bound(int[] nums, int target) { 
            	// 搜索区间为[left, right]
            	int left = 0, right = nums.length - 1;
            	while (left <= right) { 
            		int mid = left + (right -left) / 2;
            		...
            	}
            }
        
         *  因为 **\[搜索区间\]** 是两端都闭的,并且是搜索左侧边界,修改**left**和**right**的更新逻辑:
        
            if (nums[mid] == target) { 
            	right = mid -1;
            } else if (nums[mid] < target) { 
            	left = mid + 1;
            } else if (nums[mid] > target) { 
            	right = mid - 1;
            }
        
         *  由于**while**的循环终止条件为**left == right + 1,** 当**target**比**nums**中的所有元素都大时,会引起索引越界. 所以最后返回结果的代码应该检查越界情况:
        
            if (left >= nums.length || nums[left] != target) { 
            	return -1;
            }
            return left;
     *  两边都闭的 **\[搜索区间\] :**
    
        int left_bound(int[] nums, int target) { 
        	if (nums.length == 0) { 
        		return -1;
        	}
        	int left = 0, right = nums.length -1;
        
          while (left < =  right) { 	// 注意!
          	int mid = left + (right - left) / 2;
          	if (nums[mid] == target) { 
          		right = mid - 1;
          	} else if (nums[mid] < target) { 
          		left = mid + 1;
          	} else if (nums[mid] > target) { 
          		right = mid - 1;
          	}
          }
          if (left >= nums.length || nums[left] != target) { 
          	return -1;
          }
          return left;
        }
    
     *  这种算法都是两端都闭的 **\[搜索区间\],** 而且最后返回的也是**left**变量的值

# 寻找右侧边界 #

*  寻找右侧边界 **,\[搜索区间\]** 为左闭右开的算法:

int right_bound(int[] nums, int target) { 
    	if (nums.length == 0) { 
    		return -1;
    	}
    	int left = 0, right = nums.length;
    
    	while (left < right) { 
    		int mid = left + (right - left) / 2;
    		if (nums[mid] == target) { 
    			left = mid + 1;	// 注意!
    		} else if (nums[mid] < target) { 
    			left = mid + 1;
    		} else if (nums[mid] < target) { 
    			right = mid;
    		}
    	}
    	return left - 1;	// 注意!
    }

*  **问题1: 为什么这个算法能够找到右侧边界?**
    
     *  搜索右侧边界算法的关键在于 对于**nums\[mid\] == target**情况的处理:
    
        if (nums[mid] == target) { 
        	left = mid + 1;
        }
    
     *  当**nums\[mid\] == target**时,不是立即返回,而是增大 **\[搜索区间\]** 的下界**left,** 使得区间不断向右搜索,达到锁定右侧边界的目的
 *  **问题2: 为什么最后返回left-1而不是像左侧边界的函数返回left?既然是搜索右边界,应该返回right才对?**
    
     *  **while**循环的终止条件是**left == right,** 所以**left**和**right**是一样的,可以使用**right - 1**
     *  之所以返回**right - 1,** 这是搜索右侧边界的一个特殊点,关键在于**nums\[mid\] == target**的条件判断:
    
        if (num[mid] == target) { 
        	left = mid + 1;	// 由此,这里的 mid = left - 1
        }
    
     *  因为对**left**的更新必须是**left = mid + 1.** 这样**while**循环结束时 **,nums\[left\]** 一定不等于**target,** 但是**num\[left - 1\]** 可能等于**target**
 *  **问题3: 为什么没有返回-1的操作? 如果nums中不存在target这个值,如何处理?**
    
     *  因为**while**循环的终止条件是**left == right,** 也就是说**left**的取值范围是 **\[0, nums.length\],** 可以添加代码,正确地返回 **-1 :**
    
        while (left < right) { 
        	...
        }
        if (left == 0) { 
        	return -1;
        }
        return nums[left - 1] == target ? (left - 1) : -1;
 *  **问题4: 是否可以将这个算法的\[搜索区间\]统一成两端都闭的形式? 保证二分搜索算法的统一?**
    
     *  对寻找右侧边界的算法进行修改:
    
        int right_bound(int[] nums, int target) { 
        	if (nums.length == 0) { 
        		return -1;
        	}
        	int left = 0, right = nums.length -1;
        
          while (left <= right) { 
          	int mid = left + (right - left) / 2;
          	if (nums[mid] == target) { 
          		left = mid + 1;
          	} else if (nums[mid] < target) { 
          		left = mid + 1;
          	} else if (nums[mid] > target) { 
          		right = mid;
          	}
          }
          // 检查right是否越界
          if (right < 0 || nums[right] != target) { 
          	return -1;
          }
          return right;
        }
    
     *  当**target**比所有元素都小时 **,right**会被减到 **-1,** 所以需要在最后防止越界

# 统一二分查找算法 #

*  分析几种二分查找算法场景的细节差异的因果逻辑

##### 基本二分查找算法 #####

*  因为初始化时 **: right = nums.length - 1**
 *  所以决定了 **\[搜索区间\]** 是 **: \[left,right\]**
 *  所以决定了 **while(left <= right)**
 *  同时也决定了**left = mid + 1**和**right = mid - 1**
 *  因为只需要找到一个**target**的索引即可
 *  所以当**nums\[mid\] == target**时立即返回

##### 寻找左侧边界的二分查找算法 #####

*  因为初始化时 **: right = nums.length**
 *  所以决定了 **\[搜索区间\]** 是 **: \[left, right)**
 *  所以决定了**while (left < right)**
 *  同时也决定了**left = mid + 1**和**right = mid**
 *  因为需要找到**target**的最左侧索引
 *  所以当**nums\[mid\] == target**时不要立即返回
 *  而是要收缩右侧边界以锁定左侧边界

##### 寻找右侧边界的二分查找算法 #####

*  因为初始化时 **: right = nums.length**
 *  所以决定了 **\[搜索区间\]** 是 **: \[left,right)**
 *  所以决定了 **while (left < right)**
 *  同时也决定了**left = mid + 1**和**right = mid**
 *  因为需要找到**target**的最右侧索引
 *  所以当**nums\[mid\] == target**时不要立即返回
 *  而是要收缩左侧边界以锁定右侧边界
 *  因为收缩左侧边界时 **: left = mid + 1**
 *  所以最后无论返回**left**还是**right,** 最终都必须 **- 1**

##### 统一二分查找算法代码实现 #####

*  对于寻找左右边界的二分查找算法,通常使用左闭右开的 **\[搜索区间\]**
 *  **可以根据逻辑将\[搜索区间\]全都统一成两端都闭的区间,便于记忆,只要修改两处就可以变化出三种写法:**

int binary_search(int[] nums, int target) { 
    	if (nums.length == 0) { 
    		return -1;
    	} 
    	int left = 0, right = nums.length - 1;
    
    	while (left <= right) { 
    		int mid = left + (right - left) / 2;
    		if (nums[mid] < target) { 
    			left = mid + 1;
    		} else if (nums[mid] > target) { 
    			right = mid - 1;
    		} else if (nums[mid] == target) { 
    			// 直接返回
    			return mid;
    		}
    	}
    	// 直接返回
    	return -1;
    }
    
    int left_bound(int[] nums, int target) { 
    	if (nums.length == 0) { 
    		return -1;
    	}
    	int left = 0, right = nums.length - 1;
    
    	while (left <= right) { 
    		int mid = left + (right - left) / 2;
    		if (nums[mid] < target) { 
    			left = mid + 1;
    		} else if (nums[mid] > target) { 
    			right = mid - 1;
    		} else if (nums[mid] == target) { 
    			// 收缩右侧边界
    			right = mid - 1;
    		}
    	}
    	// 检查左边界left的越界情况
    	if (left >= nums.length || nums[left] != target) { 
    		return -1;
    	}
    	return left;
    }
    
    int right_bound(int[] nums, int target) { 
    	if (nums.length == 0) { 
    		return -1;
    	}
    	int left = 0, right = nums.length - 1;
    
    	while(left <= right) { 
    		int mid = left + (right - left) / 2;
    		if (nums[mid] < target) { 
    			left = mid + 1;
    		} else if (nums[mid] > target) { 
    			right = mid - 1;
    		} else if (nums[mid] == target) { 
    			// 收缩左侧边界
    			left = mid + 1;
    		}
    	}
    	// 检查right越界情况
    	if (rigth < 0 || nums[right] != target) { 
    		return -1;
    	}
    	return right;
    }

# 二分查找算法总结 #

*  分析二分查找算法时,不要出现**else,** 全部展开,使用**else if**更加方便
 *  注意 **\[搜索区间\]** 和**while**的终止条件,如果存在漏掉的元素,要在方法最后返回前做检查
 *  如果定义左闭右开的 **\[搜索区间\]** 搜索左右边界,只要在**nums\[mid\] == target**时对代码作修改即可.注意寻找右侧边界时返回值要 **- 1**
 *  如果将 **\[搜索区间\]** 全都统一成两端都闭,只要在**nums\[mid\] == target**时对代码和返回的逻辑作修改即可