2022 第 24 周
6/19/2022, 8:28:00 AM 3 min read
// 模版三「一般」情形2: 大于
class Solution {
public int search(int[] nums, int target) {
int l = -1, r = nums.length;
while(l + 1 < r){
int c = l + (r - l) / 2;
if(nums[c] <= target) l = c; // #1 更新后l及其左侧元素「必」小于等于target
else r = c; // #2 更新后r及其右侧「必」大于target
}
return r == nums.length ? -1 : r; // 处理: 相等/刚好大于/不存在
}
}
// 模版三「一般」情形1: 大于等于
class Solution {
public int search(int[] nums, int target) {
int l = -1, r = nums.length;
while(l + 1 < r){
int c = l + (r - l) / 2;
if(nums[c] < target) l = c; // #1 更新后l及其左侧元素「必」小于target
else r = c; // #2 更新后r及其右侧「必」大于等于target
}
// return (r == nums.length || nums[r] != target) ? -1 : r; // 704题的返回,处理:相等/不等
return r == nums.length ? -1 : r; // 处理: 相等/刚好大于/不存在
}
}
// 模版三「相等返回」写法
class Solution {
public int search(int[] nums, int target) {
int l = -1, r = nums.length;
while(l + 1 < r){
int c = l + (r - l) / 2;
if(nums[c] == target) return c; // 找到目标值直接返回
else if(nums[c] < target) l = c; // #1 更新后l及其左侧元素「必」小于target
else r = c; // nums[c] > target #2 更新后r及其右侧「必」大于target
}
return -1;
}
}
// 模版三「一般」情形3: 小于等于
class Solution {
public int search(int[] nums, int target) {
int l = -1, r = nums.length;``
while(l + 1 < r){
int c = l + (r - l) / 2;
if(nums[c] <= target) l = c; // #1 更新后l及其左侧元素「必」小于等于target
else r = c; // #2 更新后r及其右侧「必」大于target
}
// return (l == -1 || nums[l] != target) ? -1 : l; // 704题的返回,处理:相等/不等
return l;
}
}
// 模版三「一般」情形4: 小于
class Solution {
public int search(int[] nums, int target) {
int l = -1, r = nums.length;
while(l + 1 < r){
int c = l + (r - l) / 2;
if(nums[c] < target) l = c; // #1 更新后l及其左侧元素「必」小于target
else r = c; // #2 更新后r及其右侧「必」大于等于target
}
return l;
}
}