leecode算法--每日一题1

二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

前提条件必须满足： 目标数组必须是有序数组

所以查找操作之前必须借助排序算法进行排序

function binarySearch(arr, target) {if (typeof arr !== "object" && !Array.isArray(arr)) return -1;let left = 0,right = arr.length - 1;while (left <= right) {let mid = Math.floor((right + left) / 2); //(1)if (arr[mid] === target) {return mid;} else if (arr[mid] > target) {right = mid - 1;} else {left = mid + 1;}}return -1;
}const arr = [1, 2, 3, 4, 5, 69, 100];// const ret = binarySearch(arr, 69); //5
// const ret = binarySearch(arr, 100); //6
const ret = binarySearch(arr, 2); //1console.log(ret);

注意注释(1)那里是不严谨的写法
严谨的写法如下

 let mid = Math.floor((right - left) / 2) + left;

right + left有可能超出js中的数值最大值。这样写就可以保证查询的数据任意大