海南省网站建设_网站建设公司_Oracle_seo优化

详细解释可以看这篇文章https://www.cnblogs.com/labuladong/p/12320448.html。

一、基础框架：二分查找通用模板

给出二分查找的核心框架，明确关键可变细节（用...标记），并强调“用else if替代else”以清晰展现逻辑：

intbinarySearch(int[]nums,inttarget){intleft=0,right=...;// 细节1：right初始化while(...){// 细节2：循环终止条件intmid=(left+right)/2;if(nums[mid]==target){...}// 细节3：找到目标后的处理elseif(nums[mid]<target){left=...}// 细节4：左边界更新elseif(nums[mid]>target){right=...}// 细节5：右边界更新}return...;// 细节6：最终返回值}

注：暂忽略mid计算的溢出问题（提及可参考前文解决）。

二、三类典型场景：细节拆解与逻辑分析

网页分三类场景，逐一解析“right初始化、循环条件、边界更新、返回值”等细节的差异及原因，核心是围绕“搜索区间定义”展开逻辑推导。

1. 场景1：寻找一个数（基本二分搜索）

• 功能：搜索目标值，存在则返回索引，否则返回-1。
• 核心代码：

  intbinarySearch(int[]nums,inttarget){intleft=0;intright=nums.length-1;// 搜索区间：[left, right]（两端闭）while(left<=right){// 终止条件：left = right + 1（区间为空，无遗漏）intmid=(left+right)/2;if(nums[mid]==target)returnmid;// 找到即返回（仅需一个目标）elseif(nums[mid]<target)left=mid+1;// 排除mid，新区间[mid+1, right]elseif(nums[mid]>target)right=mid-1;// 排除mid，新区间[left, mid-1]}return-1;// 区间为空，未找到}

• 关键细节解释：
  • 为何while(left <= right)？因搜索区间是[left, right]，终止时区间为空（如[3,2]），无遗漏；若用<，终止时区间为[left, left]（非空），可能漏掉目标。
  • 为何left=mid+1/right=mid-1？因mid已验证非目标，需从搜索区间中排除。
• 缺陷：无法找到目标的“左侧边界”或“右侧边界”（如[1,2,2,2,3]中target=2，无法返回索引1或3）。
  实例
  输入
  数组 nums = [1, 3, 5, 7, 9, 11]，目标值 target = 7（若目标不存在：target = 4，预期返回 - 1）
  分步推导（以找 7 为例）
  初始化：搜索区间 [left, right] = [0, 5]（闭区间，覆盖所有元素）
  第一次循环：
  mid = (0+5)/2 = 2，nums[2] = 5
  因 5 < 7，排除左半区（mid 已验证非目标），更新 left = mid+1 = 3，新区间 [3,5]
  第二次循环：
  mid = (3+5)/2 = 4，nums[4] = 9
  因 9 > 7，排除右半区，更新 right = mid-1 = 3，新区间 [3,3]
  第三次循环：
  满足 left <= right（3<=3），mid = 3，nums[3] = 7
  找到目标，直接返回 mid = 3（符合预期）
  若目标不存在（找 4）
  初始区间 [0,5]，第一次循环 mid=2（5>4），right=1，区间 [0,1]
  第二次循环 mid=0（1<4），left=1，区间 [1,1]
  第三次循环 mid=1（3<4），left=2，区间 [2,1]（空区间）
  循环终止，返回 -1（符合预期）

2. 场景2：寻找左侧边界（如target=2返回最左索引1）

• 功能：找到目标值的最左侧索引，若无则返回-1（返回值也可理解为“小于target的元素个数”）。
• 核心代码：

  intleft_bound(int[]nums,inttarget){if(nums.length==0)return-1;intleft=0;intright=nums.length;// 搜索区间：[left, right)（左闭右开）while(left<right){// 终止条件：left = right（区间为空，无遗漏）intmid=(left+right)/2;if(nums[mid]==target)right=mid;// 不返回，收缩右边界（锁定左侧）elseif(nums[mid]<target)left=mid+1;// 新区间[mid+1, right)elseif(nums[mid]>target)right=mid;// 新区间[left, mid)}// 补全“未找到”判断：left范围是[0, nums.length]if(left==nums.length)return-1;// target比所有数大returnnums[left]==target?left:-1;// 验证是否为目标}

• 关键细节解释：
  • 为何right = nums.length？因搜索区间是[left, right)，right取nums.length可覆盖“target比所有数大”的场景（如返回4表示小于target的元素有4个）。
  • 为何while(left < right)？终止时left=right，区间[left, left)为空，无遗漏。
  • 为何nums[mid]==target时right=mid？不立即返回，而是缩小右边界，在[left, mid)中继续搜索，锁定最左侧目标。
  • 为何返回left？终止时left=right，二者等价。

3. 场景3：寻找右侧边界（如target=2返回最右索引3）

• 功能：找到目标值的最右侧索引，若无则返回-1。
• 核心代码：

  intright_bound(int[]nums,inttarget){if(nums.length==0)return-1;intleft=0,right=nums.length;// 搜索区间：[left, right)（左闭右开）while(left<right){intmid=(left+right)/2;if(nums[mid]==target)left=mid+1;// 不返回，收缩左边界（锁定右侧）elseif(nums[mid]<target)left=mid+1;// 新区间[mid+1, right)elseif(nums[mid]>target)right=mid;// 新区间[left, mid)}// 补全“未找到”判断：left范围是[0, nums.length]if(left==0)return-1;// target比所有数小returnnums[left-1]==target?(left-1):-1;// 需减1（因left已超右侧边界）}

• 关键细节解释：
  • 为何nums[mid]==target时left=mid+1？不立即返回，缩小左边界，在[mid+1, right)中继续搜索，锁定最右侧目标。
  • 为何返回left-1？因left更新为mid+1，终止时nums[left]必非目标，而nums[left-1]可能是目标（如[1,2,2,2,3]中，找到最后一个2后left会指向4，需减1得3）。

三、核心总结：细节差异的因果逻辑

三类场景的细节差异，本质由“搜索区间定义”决定，形成如下因果链：

实例解析与代码验证

二分查找的“细节魔鬼”体现在搜索区间定义上，不同场景对应不同的区间逻辑。以下通过「具体需求+输入输出+分步推导」，为三种场景逐一举例，帮你直观理解边界处理的本质。

场景1：寻找一个数（基本二分搜索）

核心需求

在有序无重复/有重复数组中，判断目标值是否存在，存在则返回任意一个目标值的索引，不存在则返回-1（仅需“找到与否”，不关心目标的位置范围）。

实例

输入

数组nums = [1, 3, 5, 7, 9, 11]，目标值target = 7
（若目标不存在：target = 4，预期返回-1）

分步推导（以找7为例）

1. 初始化：搜索区间[left, right] = [0, 5]（闭区间，覆盖所有元素）
2. 第一次循环：
   mid = (0+5)/2 = 2，nums[2] = 5
   因5 < 7，排除左半区（mid已验证非目标），更新left = mid+1 = 3，新区间[3,5]
3. 第二次循环：
   mid = (3+5)/2 = 4，nums[4] = 9
   因9 > 7，排除右半区，更新right = mid-1 = 3，新区间[3,3]
4. 第三次循环：
   满足left <= right（3<=3），mid = 3，nums[3] = 7
   找到目标，直接返回mid = 3（符合预期）

若目标不存在（找4）

1. 初始区间[0,5]，第一次循环mid=2（5>4），right=1，区间[0,1]
2. 第二次循环mid=0（1<4），left=1，区间[1,1]
3. 第三次循环mid=1（3<4），left=2，区间[2,1]（空区间）
4. 循环终止，返回-1（符合预期）

场景2：寻找左侧边界

核心需求

在有序有重复数组中，找到目标值的「最左侧索引」（即第一个等于目标的元素位置）；若目标不存在，返回-1（需“锁定目标的起始范围”，如统计目标出现次数时需先找左边界）。

实例

输入

数组nums = [1, 2, 2, 2, 3, 4]，目标值target = 2
（若目标不存在：target = 5，预期返回-1）

分步推导（以找2的左边界为例）

1. 初始化：搜索区间[left, right) = [0, 6)（左闭右开，right取数组长度，覆盖“目标比所有数大”的场景）
2. 第一次循环：
   mid = (0+6)/2 = 3，nums[3] = 2
   找到目标但不返回，需收缩右边界锁定左半区，更新right = mid = 3，新区间[0,3)
3. 第二次循环：
   mid = (0+3)/2 = 1，nums[1] = 2
   继续收缩右边界，更新right = mid = 1，新区间[0,1)
4. 第三次循环：
   mid = (0+1)/2 = 0，nums[0] = 1
   因1 < 2，排除左半区，更新left = mid+1 = 1，新区间[1,1)（空区间）
5. 验证返回：
   left = 1，nums[1] = 2，返回1（即2的最左侧索引，符合预期）

若目标不存在（找5）

1. 初始区间[0,6)，第一次循环mid=3（2<5），left=4，区间[4,6)
2. 第二次循环mid=5（4<5），left=6，区间[6,6)（空区间）
3. 验证返回：left = 6（等于数组长度），返回-1（符合预期）

场景3：寻找右侧边界

核心需求

在有序有重复数组中，找到目标值的「最右侧索引」（即最后一个等于目标的元素位置）；若目标不存在，返回-1（与左边界配合可计算目标出现次数：右边界 - 左边界 + 1）。

实例

输入

数组nums = [1, 2, 2, 2, 3, 4]，目标值target = 2
（若目标不存在：target = 0，预期返回-1）

分步推导（以找2的右边界为例）

1. 初始化：搜索区间[left, right) = [0, 6)（左闭右开，同左边界场景）
2. 第一次循环：
   mid = (0+6)/2 = 3，nums[3] = 2
   找到目标但不返回，需收缩左边界锁定右半区，更新left = mid+1 = 4，新区间[4,6)
3. 第二次循环：
   mid = (4+6)/2 = 5，nums[5] = 4
   因4 > 2，排除右半区，更新right = mid = 5，新区间[4,5)
4. 第三次循环：
   mid = (4+5)/2 = 4，nums[4] = 3
   因3 > 2，排除右半区，更新right = mid = 4，新区间[4,4)（空区间）
5. 验证返回：
   left = 4，需检查left-1 = 3（因left已超右边界），nums[3] = 2，返回3（即2的最右侧索引，符合预期）

若目标不存在（找0）

1. 初始区间[0,6)，第一次循环mid=3（2>0），right=3，区间[0,3)
2. 第二次循环mid=1（2>0），right=1，区间[0,1)
3. 第三次循环mid=0（1>0），right=0，区间[0,0)（空区间）
4. 验证返回：left = 0（等于0），返回-1（符合预期）

三种场景实例对比总结