左闭右闭
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int middle =left + (right - left) /2;
if (target > nums[middle]) {
left = middle + 1;
} else if (target < nums[middle]) {
right = middle - 1;
} else {
return middle;
}
}return -1;
}
}
middle = (left + right)/2 与 left+ (right - left)/2
两个最大值的int类型相加,可能会造成越界,目的是求均值,故先减后加,防止越界
左闭右开
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length;
while (left < right) {
int middle =left + (right - left) /2;
if (target > nums[middle]) {
left = middle + 1;
} else if (target < nums[middle]) {
right = middle ;
} else {
return middle;
}
}return -1;
}
}
一是初始right的取值,当左闭右开时,不包括右边的区间,应该等于nums.length
例如有四个数字,0,1,2,3,左闭右闭 [0,3],左闭右开 [0,4) 才能取到相同的数字
二是 目标在左半区间,因为右开,所以搜索时也不包含右边界,故此时搜索区间应该是[0,middle)
左开右闭
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int middle =left + (right - left) /2;
if (target > nums[middle]) {
left = middle + 1;
} else if (target < nums[middle]) {
right = middle - 1 ;
} else {
return middle;
}
}return -1;
}
}
一同上
二 left左区间取值,因为middle = (right + left) /2 是向下取整的,导致后续区间的middle取不对,所以需要middle +1