一、题目
二、解题
注:本文均是Java代码
1、双闭区间写法
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int middle = (left + right) >>> 1;
if (target < nums[middle]) {
right = middle - 1;
}
else if (nums[middle] < target) {
left = middle + 1;
}
else {
return middle;
}
}
return -1;
}
}
2、左闭右开区间写法
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int middle = (left + right) >>> 1;
if (target < nums[middle]) {
right = middle;
}
else if (nums[middle] < target) {
left = middle + 1;
}
else {
return middle;
}
}
return -1;
}
}
3、左开右闭区间写法
class Solution {
public int search(int[] nums, int target) {
int left = -1, right = nums.length - 1;
while (left < right) {
int middle = (left + right + 1) >>> 1;
if (target < nums[middle]) {
right = middle - 1;
}
else if (nums[middle] < target) {
left = middle;
}
else {
return middle;
}
}
return -1;
}
}
4、双开区间写法
public int search(int[] nums, int target) {
int left = -1, right = nums.length;
while (left + 1 < right) {
int middle = (left + right) >>> 1;
if (target < nums[middle]) {
right = middle;
}
else if (nums[middle] < target) {
left = middle;
}
else {
return middle;
}
}
return -1;
}
}
5、说明
四种写法本质上并没有太大差别,只是定义的区间开闭不同,在解决一些具体问题的时候可以根据题目定义不同开闭区间,使用技巧快速解题。
尤其注意左开右闭和左闭右开区间的偏移问题。
最容易出现的两个报错就是数组越界和死循环超时。
—定要记住最基础版的双闭区间写法,其它写法都是根据这个的变形。
参考博客:
【玩转二分查找Ⅰ】左闭右闭型,左开右闭型,左闭右开型(动图演绎)_数学左闭右开-CSDN博客
二分查找的细节(左闭右闭、左闭右开、左开右闭)及其两段性-CSDN博客
参考视频:
搜索旋转排序数组【基础算法精讲 05】_哔哩哔哩_bilibili
标签:二分,right,target,nums,704,middle,int,LeetCode,left From: https://blog.csdn.net/qq_63939626/article/details/137353961