综述
以记忆为目的，避免细节纠结。 寻找左右边界代码几乎一样，只是最后返回值的不同，有时需要返回-1有时需要返回相关索引。
经典题目代码
leetcode题目34第一个和最后一个位置
public static int[] searchRange(int[] nums
, int target
) {
int[] res
= new int[2];
res
[0] = findleft(nums
,target
);
res
[1] = findright(nums
,target
);
return res
;
}
public static int findright(int[] nums
, int target
) {
int left
= 0,right
= nums
.length
-1;
while (left
<=right
){
int mid
= (left
+((right
-left
)>>1));
if (nums
[mid
]==target
){
left
= mid
+1;
}
else if (nums
[mid
]>target
){
right
= mid
-1;
}
else {
left
= mid
+1;
}
}
if (right
<0||nums
[right
]<target
)
return -1;
else
return nums
[right
]==target
?right
:-1;
}
public static int findleft(int[] nums
, int target
) {
int left
= 0,right
= nums
.length
-1;
while (left
<=right
){
int mid
= (left
+((right
-left
)>>1));
if (nums
[mid
]==target
){
right
= mid
-1;
}
else if (nums
[mid
]>target
){
right
= mid
-1;
}
else {
left
= mid
+1;
}
}
if (left
>=nums
.length
||nums
[left
]>target
)
return -1;
else
return nums
[left
]==target
?left
:-1;
}
标准
题目
x的平方根第一个错误版本
public int firstBadVersion(int n
) {
int left
= 1,right
= n
;
while(left
<right
){
int mid
= left
+((right
-left
)>>1);
if (isBadVersion(mid
)){
right
= mid
;
}else
left
= mid
+1;
}
if (left
>n
||!isBadVersion(left
))
return n
+1;
return left
;
}
思路
代码
public static int searchInsert(int[] nums
, int target
) {
int left
= 0,right
= nums
.length
-1;
while (left
<=right
){
int mid
= (left
+((right
-left
)>>1));
if (nums
[mid
]==target
){
right
= mid
-1;
}
else if (nums
[mid
]>target
){
right
= mid
-1;
}
else {
left
= mid
+1;
}
}
return mid
;
}
左边界
思路
左边界需要判断left是否超出边界/left处的值是否小于进行left返回。
题目
leetcode题目35
模板
public static int searchInsert(int[] nums
, int target
) {
if (nums
.length
==1)
return nums
[0]>=target
?0:1;
int left
= 0,right
= nums
.length
-1;
while (left
<=right
){
int mid
= (left
+((right
-left
)>>1));
if (nums
[mid
]==target
){
right
= mid
-1;
}
else if (nums
[mid
]>target
){
right
= mid
-1;
}
else {
left
= mid
+1;
}
}
if (left
>=nums
.length
||nums
[left
]<target
)
return nums
.length
;
else
return left
;
}
右边界
思路
判断right和0以及right处值和target大小。
模板
public static int findright(int[] nums
, int target
) {
int left
= 0,right
= nums
.length
-1;
while (left
<=right
){
int mid
= (left
+((right
-left
)>>1));
if (nums
[mid
]==target
){
left
= mid
+1;
}
else if (nums
[mid
]>target
){
right
= mid
-1;
}
else {
left
= mid
+1;
}
}
if (right
<0||nums
[right
]<target
)
return 0;
else
return right
;
}
