第 30 期(算法-搜索)：二分搜索算法

[wingmeng]

题目：

请使用 二分搜索算法 编写函数 binarySearch，实现类似 indexOf 的功能。要求：

• 不要用递归方式实现；
• 避免产生副作用（即不能修改原数组）。

/**
 * @param {array} arr - 按升序排列的普通数组
 * @param {number} target - 需要在 arr 中搜索的目标值
 * @return {number} 返回 target 在 arr 中的索引值，如不存在，则返回 -1
 */
function binarySearch(arr, target) {
  // 你的代码
}

测试数据：

const test = [1, 3, 8, 9, 27, 34, 128, 275];

binarySearch(test, 128);  // 6
binarySearch(test, 30);  // -1

---

参考答案：

function binarySearch(arr, target) {
  let startIdx = 0;
  let endIdx = arr.length - 1;
  let midIdx = Math.floor((startIdx + endIdx) / 2);

  while(endIdx - startIdx > 1) {
    switch(target) {
      case arr[startIdx]: return startIdx;
      case arr[endIdx]: return endIdx;
      case arr[midIdx]: return midIdx;
    }

    if (target > arr[midIdx]) {  // 右边找
      startIdx = midIdx;
    } else if (target < arr[midIdx]) {  // 左边找
      endIdx = midIdx;
    }

    midIdx = Math.floor((startIdx + endIdx) / 2);
  }

  return -1;
}