读题思路
首先，题目中明确说明输入的数组为 有序的（升序）整型数组、并且无重复元素，所以如题所示，那自然就是用二分查找法来查找咯。
解题思路
二分法：
- 找到中间值，中值下标为mid（初始值就是总数/2），查找的总下标为flag（初始值为总数）
- 将要查找的值（目标值）与中间值进行比较；根据大小的结果，调整mid值和总下标，还有将下标左移或右移（+1 or -1）
- 重复步骤1,2；直至找到目标值 或 中值mid与总下标发生矛盾。
出现的问题
情况一（JS）：
var search = function(nums, target) {
let flagR = nums.length, flagL = 0
let mid = Math.round((flagR-flagL) / 2) //考虑到奇数除以2会是小数，所以要取整
while(mid > flagL & mid < flagR){//能够继续下去的条件是mid在flag间
if(nums[mid] == target){ //中值就是目标值 那就皆大欢喜 直接输出
return mid
}
else if(nums[mid] < target){ //因为是升序，所以这里意味着目标值在中值右边，所以flag调整为右端；若为降序则相反
flagL = mid
mid = Math.round((flagR-flagL) / 2)
}
else if(nums[mid] > target){ //同理，flag调整为左端
flagR = mid
mid = Math.round((flagR-flagL) / 2)
}
else{
return -1
}
//console.log(mid)
}
};
问题：
mid值的下标并没有如期改变。
以nums = [-1,0,3,5,9,12]，target = 9为例
第一次迭代（初始化）：
flagL=0, flagR=6
此时mid=3，nums[3]=5, < target 9，所以符合条件2（第一个else if）
第二次迭代：
flagL=3, flagR=6
原因：
在多次迭代时，mid值没有正确改变。
解决方法：
在flag移到右端的情况下，mid的下标需要+=；而左端不需要
mid = Math.round((flagR-flagL) / 2)
改为
mid += Math.round((flagR-flagL) / 2)
在修改过程中发现flag值初始化也有问题，
应改为flagR = nums.length-1，因为是下标的范围嘛。
还有return -1的位置也不恰当。
情况二（JS）：
修改后的代码提交部分成功
var search = function(nums, target) {
let flagR = nums.length-1, flagL = 0
let mid = Math.round((flagR-flagL) / 2) //考虑到奇数除以2会是小数，所以要取整
while(mid > flagL & mid < flagR){ //能够继续下去的条件是mid在flag间
if(nums[mid] == target){ //中值就是目标值 那就皆大欢喜 直接输出
return mid
}
else if(nums[mid] < target){ //因为是升序，所以这里意味着目标值在中值右边，所以flag调整为右端；若为降序则相反
flagL = mid
mid += Math.round((flagR-flagL) / 2)
}
else if(nums[mid] > target){ //同理，flag调整为左端
flagR = mid
mid = Math.round((flagR-flagL) / 2)
}
console.log(mid)
}
return -1
};
问题：
报错
原因：
极端情况没考虑。
考虑极端情况：
- 如报错图所示，数组长度为1
- target在首或尾。所以就是考虑循环边界的问题。
解决方法：
首先，对于数组长度为1的情况，主要是flagL和flagR需要移位，flagL = mid+1，flagR = mid-1，还有while循环条件改为mid >= flagL & mid <= flagR；
接下来，仍旧报错，是target在首或尾的极端情况。如：nums=[-1,0,5], target=5
经过分析，问题出在
当flagL=2,flagR=2, mid = 1+Math.round(0.5)时，这个mid其实就不准了。所以要改变mid计算方式。
mid = Math.round((flagR+flagL) / 2)
经过优化后，JS的解法为
var search = function(nums, target) {
let flagR = nums.length-1, flagL = 0
// let mid = Math.round((flagR+flagL) / 2) //考虑到奇数除以2会是小数，所以要取整
while(flagL <= flagR){ //能够继续下去的条件是mid在flag间,也就是flagL要小于flagR
mid = Math.round((flagR+flagL) / 2)
if(nums[mid] == target){ //中值就是目标值 那就皆大欢喜 直接输出
return mid
}
else if(nums[mid] < target){ //因为是升序，所以这里意味着目标值在中值右边，所以flag调整为右端；若为降序则相反
flagL = mid+1
}
else if(nums[mid] > target){ //同理，flag调整为左端
flagR = mid-1
}
}
return -1
};
优化后，时间也变短了：
优化前 vs 优化后
Python解法为
class Solution(object):
def search(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
return -1
发现用Python无论是时间还是内存都比JS少诶。
提交结果对比一览
总结
今天算是完全自己从头到尾刷了一道简单的LeetCode题，感觉很不错。
以前一直以为自己对二分法很懂了，现在才发现是纸上谈兵，写起代码来还是有坑的。
不过这之后应该算是能说对二分法彻底掌握了哈哈哈！
网友评论