巩固练习二分查找-35/34/69/367
35.搜索插入位置
解题思路
与704不同的是，在找不到目标值的索引时返回的不是-1而是它将会被按顺序插入的位置，所以前面不变只改后面的。
对报错例子nums=[1,3,5,6], target=2进行分析，可以知道只需在最后一步对mid进行+1或-1的操作就能得到应插入的位置。
因为最后的mid值已经是应该插入的附近（+1-1）位置，具体在左还是在右就可以看mid和flagL,flagR的大小关系。如果最后flagL比mid大，说明最后一次迭代是nums[mid] < target情况，那么就说明target值在nums[mid]右侧，所以最后的索引值应该是+1。反之，则为-1。
所以,将
return -1
更改为
if(flagL>mid){
return mid + 1
}
else if(mid > flagR){
return mid -1
}
出现的问题
简单这么改不行，在情况mid > flagR下可能会出现mid=0，那输出应该为0而不是-1.
而且，mid+1没问题，但mid-1要注意总数其实增加了1的问题，要是直接-1，那么左边所有数的索引都会变动-1，应该注意是插入！
所以！在总数+1，而本来是mid -1，这样之后其实抵消了！
只用返回mid就可以了！
JavaScript解法代码
var searchInsert = function(nums, target) {
let flagL=0,flagR=nums.length-1
while(flagL <= flagR){
mid = Math.round((flagL+flagR) / 2)
if(nums[mid] == target){
return mid
}
else if(nums[mid] < target){
flagL = mid + 1
}
else if(nums[mid] > target){
flagR = mid - 1
}
}
if(flagL>mid){
return mid + 1
}
else if(mid > flagR){
return mid //总数+1，再-1 等于不变
// if(mid == nums.length-1){
// return mid
// }
// if(mid-1 >= 0){
// return mid - 1
// }
// else{
// return 0
// }
}
};
Python解法代码
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
flagL = 0
flagR = len(nums)-1
while(flagL<=flagR):
mid = int((flagL+flagR) / 2)
if(nums[mid] == target):
return mid
elif(nums[mid] < target):
flagL = mid+1
elif(nums[mid] > target):
flagR = mid-1
if(flagL>mid):
return mid + 1
elif(mid > flagR):
return mid
提交结果一览
34. 在排序数组中查找元素的第一个和最后一个位置
解题思路
确实是二分查找法的变体。不同点在于请你找出给定目标值在数组中的开始位置和结束位置，所以数组里的被查找值大概率是不止一个的，如nums = [5,7,7,8,8,10]。
所以，
第一步：肯定是找到target值的位置（这个值可能在一系列相同值的任意位置）
第二步：找到了一个位置后，说明附近应该都是它，所以用循环向左和向右的找出左右边界的位置。
出现的问题
情况一(JS)
在写第一步代码的时候，直接复制了，没有仔细确认，所以直接return了。。。导致后面都不行。所以一定要仔细检查！
情况二(Python)
边界情况，or极端情况未考虑，如nums=[], target=0，nums=[1], target=1。
加上边界：
if(temp-1 >= 0 and nums[temp-1] == target ): #左滑找start
if(temp+1 < len(nums) and nums[temp+1] == target): #右滑找end
JavaScript解法代码
var searchRange = function(nums, target) {
let flagL = 0, flagR = nums.length-1
let start = end = -1 //没有这个数，返回-1，-1
//第一步
while(flagL<=flagR){
mid = Math.round((flagR+flagL) / 2)
if(nums[mid] == target){
break
}
else if(nums[mid] < target){
flagL = mid + 1
}
else if(nums[mid] > target){
flagR = mid - 1
}
}
// 如果找到了一个位置，说明附近应该都是它，所以想到用循环
//第二步
if(nums[mid] == target){
temp = mid
while(nums[temp] == target){ //如果有这个数
if(nums[temp-1] == target){ //左滑找start
start = temp-1
temp -= 1
}
else{
start = temp
break
}
}
temp = mid
while(nums[temp] == target){ //如果有这个数
if(nums[temp+1] == target){ //右滑找end
end = temp+1
temp += 1
}
else{
end = temp
break
}
}
}
return [start,end]
};
Python解法代码
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
flagL = 0
flagR = len(nums)-1
start = end = -1
if(len(nums) == 0):
return [start,end]
while(flagL<=flagR):
mid = int((flagL+flagR) / 2)
if(nums[mid] == target):
break
elif(nums[mid] < target):
flagL = mid+1
elif(nums[mid] > target):
flagR = mid-1
print(mid)
if(nums[mid] == target):
if(len(nums) == 1): #只有1个，却就是目标值
return [0, 0]
temp = mid
while(nums[temp] == target): #如果有这个数
if(temp-1 >= 0 and nums[temp-1] == target ): #左滑找start
start = temp-1
temp -= 1
else:
start = temp
break
temp = mid
while(nums[temp] == target): #如果有这个数
if(temp+1 < len(nums) and nums[temp+1] == target): #右滑找end
end = temp+1
temp += 1
else:
end = temp
break
return [start, end]
69.x 的平方根
解题思路
乍一眼看好像和二分查找没关系，但是仔细一想，算术平方根就是找一个数a，使得a * a的结果最接近x。
所以，改一下判断条件即可。
出现的问题
情况一(JS)
它的取整，与四舍五入不同。比如8，3的平方相较于2的平方更接近8，实际上8的算术平方根是2.82842也更接近3，但取整后它会输出2。所以，这里要有个如何取整的问题。
思路里想的太简单了，不是a * a的结果最接近x，a就是答案。而要细分不同的情况：
-
a*a > x，则此时a一定不是要找的数，会大于1 -
a*a = x，则此时a就是要找的数 -
a*a < x，则此时a大概率是要找的数
所以，取整要向下取整，用Math.floor()
var mySqrt = function(x) {
let flagL=0,flagR=x
while(flagL < flagR){
mid = Math.floor((flagR+flagL) / 2)
multiple = mid * mid
if(multiple == x){
return mid
}
else if(multiple < x){
flagL = mid + 1
}
else if(multiple > x){
flagR = mid - 1
}
}
return mid
};
情况二(JS)
特殊情况未考虑。比如0,1。所以加上
if(x<2){
return x
}
情况三(JS)
还是错，看了标准答案。它的flagR的初始值是Math.ceil(x / 2 + 1)，后面mid的计算是Math.floor(left + (right - left) / 2)。
flagR这么初始化能理解，这个a一定是比x小的，比中值大带给后面操作的空间。
情况四(JS)
还是错，看了标准答案。
最后return的不是mid，是right(flagR)！
反思
这道题并没有思考明白，反而是看别人的答案，甚至别人的答案都不能彻底理解。
主要问题在于边界值的取值。
这个视频讲得很好，是二分查找的通解，有图像演示更易懂。
（明天再来自己写一遍！）
成功了！而且这个解法不用考虑太多边界的问题，只要明白你要的是什么，最后return什么是最重要的！Nice！
新方法前后对比
JavaScript解法代码
var mySqrt = function(x) {
let flagL = -1, flagR = x
if(x < 2){
return x
}
while(flagL+1 != flagR){
mid = Math.floor((flagL+flagR) / 2)
if(mid * mid === x){
return mid
}
if(mid * mid > x){
flagR = mid
}
else{
flagL = mid
}
}
return flagL
};
Python解法代码
import math
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
flagL = -1
flagR = x
if(x < 2):
return x
while(flagL+1 != flagR):
mid = int(math.floor((flagL+flagR) / 2))
if(mid * mid == x):
return mid
if(mid * mid > x):
flagR = mid
else:
flagL = mid
return flagL
367. 有效的完全平方数
解题思路
掌握了这种通用方法，很快就做出来了哈哈哈哈哈。
都是一样的。
JavaScript解法代码
var isPerfectSquare = function(num) {
let flagL = -1, flagR = num
if(num < 2){
return true
}
while(flagL+1 != flagR){
mid = Math.floor((flagL+flagR) / 2)
if(mid * mid === num){
return true
}
if(mid * mid > num){
flagR = mid
}
else{
flagL = mid
}
}
return false
};
Python解法代码
import math
class Solution(object):
def isPerfectSquare(self, num):
"""
:type num: int
:rtype: bool
"""
flagL = -1
flagR = num
if(num < 2):
return True
while(flagL+1 != flagR):
mid = int(math.floor((flagL+flagR) / 2))
if(mid * mid == num):
return True
if(mid * mid > num):
flagR = mid
else:
flagL = mid
return False
总结
- 二分查找法的时间复杂度是 O(log n)
- 可使用二分查找法的条件是： 无重复元素的有序(升序or降序) 排列数组
- 通用二分查找法(红蓝区间,蓝在左，红在右)的伪代码：
l = -1, r = n
while l+1 != r:
m = (l+r) / 2
if isBlue(m):
l = m
else:
r = m
return l or r //根据题意具体看
