二分法学习

[mengjoy]

二分法适合有序的数组

1. 二分法顾名思义，将数组分成两半进行查找，因为数组是有序的，可以判断当前middle值与target的比较。
2. middle > target时，当前数组为升序，那么target应属于前半段到middle的范围内
3. middle<target时，当前数组若为升序，那么target应属于后半段的范围内
4. 二分法使用的各种算法，需要注意边界条件以及边界值，middle+1 or middle -1,midlle是向上取整还是向下取整。

var search = function(nums, target) { let left = 0, right = nums.length - 1, tmp; while(left <= right) { tmp = Math.floor((left + right) / 2) if(nums[tmp] === target) { return tmp; } // 相当于已经比较完mid，就不再使用这个值 if(nums[tmp] < target) { left = tmp+ 1 } else { right = tmp - 1 } } return -1 };