二分查找

1.二分查找步骤

要求被搜索的数据结构已排序。 (1) 选择数组的中间值 (2) 如果选中值是待搜索值，那么算法执行完毕（值找到了）。 (3) 如果待搜索值比选中值要小，则返回步骤 1 并在选中值左边的子数组中寻找（较小）。 (4) 如果待搜索值比选中值要大，则返回步骤 1 并在选种值右边的子数组中寻找（较大）。

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid; // 找到目标值，返回索引
    } else if (arr[mid] < target) {
      left = mid + 1; // 目标值在右侧
    } else {
      right = mid - 1; // 目标值在左侧
    }
  }

  return -1; // 目标值未找到
}

const arr = [0, 13, 21, 35, 46, 52, 68, 77, 89, 94];
console.log(binarySearch(arr, 68)); // 输出：6
console.log(binarySearch(arr, 1)); // 输出：-1

时间复杂度

二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],
则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.
时间复杂度即是while循环的次数。
总共有n个元素，
渐渐跟下去就是n,n/2,n/4,....n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数
由于你n/2^k取整后>=1
即令n/2^k=1
可得k=log2n,（是以2为底，n的对数）
所以时间复杂度可以表示O(h)=O(log2n) 或 忽略底数：O(log(n))  快速排序是O(nlog(n)

方式 1：非递归:

//arr:数组;key:查找的元素
function search(arr, key) {
  //初始索引开始位置和结束位置
  var start = 0,
    end = arr.length - 1;
  while (start <= end) {
    //取上限和下限中间的索引
    var mid = parseInt((end + start) / 2);
    if (key == arr[mid]) {
      //如果找到则直接返回
      return mid;
    } else if (key > arr[mid]) {
      //如果key是大于数组中间索引的值则将索引开始位置设置为中间索引+1
      start = mid + 1;
    } else {
      //如果key是小于数组中间索引的值则将索引结束位置设置为中间索引-1
      end = mid - 1;
    }
  }
  //如果在循环内没有找到查找的key(start<=end)的情况则返回-1
  return -1;
}
var arr = [0, 13, 21, 35, 46, 52, 68, 77, 89, 94];
search(arr, 68); //6
search(arr, 1); //-1

方式 2：递归:

//arr:数组;key:查找的元素;start:开始索引;end:结束索引
function search2(arr, key, start, end) {
  //首先判断当前起始索引是否大于结束索引,如果大于说明没有找到元素返回-1
  if (start > end) {
    return -1;
  }
  //如果手动调用不写start和end参数会当做第一次运行默认值
  //三元表达式:如果不写end参数则为undefined说明第一次调用所以结束索引为arr.length-1
  //如果是递归调用则使用传进来的参数end值
  var end = end === undefined ? arr.length - 1 : end;
  //如果 || 前面的为真则赋值start,如果为假则赋值后面的0
  //所以end变量没有写var end = end || arr.length-1;这样如果递归调用时候传参end为0时会被转化为false,导致赋值给arr.length-1造成无限循环溢出;
  var start = start || 0;
  //取中间的索引
  var mid = parseInt((start + end) / 2);

  console.log("start", start, "end", end, "mid", mid);
  // start 0 end 9
  // start 5 end 9

  if (key == arr[mid]) {
    //如果找到则直接返回
    console.log("如果找到则直接返回");
    return mid;
  } else if (key < arr[mid]) {
    //如果key小于则递归调用自身,将结束索引设置为中间索引-1
    console.log("如果key小于则递归调用自身,将结束索引设置为中间索引-1");
    return search2(arr, key, start, mid - 1);
  } else {
    console.log("如果key大于则递归调用自身,将起始索引设置为中间索引+1");
    //如果key大于则递归调用自身,将起始索引设置为中间索引+1
    return search2(arr, key, mid + 1, end);
  }
}
// length 9
var arr = [0, 13, 21, 35, 46, 52, 68, 77, 89, 94];
search2(arr, 77); //7
/*
log:
start 0 end 9 mid 4
VM321:30 如果key大于则递归调用自身,将起始索引设置为中间索引+1
VM321:17 start 5 end 9 mid 7
VM321:23 如果找到则直接返回
* */
search2(arr, 99); //-1

二分查找:调用 sort 排序

function binarySearch(arr, element) {
  console.log({ arr, element });
  let left = 0;
  let right = arr.length - 1;

  debugger;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === element) {
      return mid;
    } else if (arr[mid] < element) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

const arr = [2, 3, 1, 5, 7, 9, 8];
const element = 8;
const index = binarySearch(
  arr.sort((a, b) => a - b),
  element
);

if (index === -1) {
  console.log(`The element ${element} is not found in the array.`);
} else {
  console.log(
    `The element ${element} is found at index ${index} in the array.`
  );
}

二分查找:自定义排序，然后二分

// quickSort start
// quickSort start
function swap(array, index1, index2) {
  const aux = array[index1];
  array[index1] = array[index2];
  array[index2] = aux;
}

function partition(array, left, right, compareFn) {
  const pivot = array[Math.floor((right + left) / 2)]; // 8
  let i = left; // 9
  let j = right; // 10

  while (i <= j) {
    // 11
    while (compareFn(array[i], pivot) === Compare.LESS_THAN) {
      // 12
      i++;
    }
    while (compareFn(array[j], pivot) === Compare.BIGGER_THAN) {
      // 13
      j--;
    }
    if (i <= j) {
      // 14
      swap(array, i, j); // 15
      i++;
      j--;
    }
  }
  return i; // 16
}

function quick(array, left, right, compareFn) {
  let index; // 1
  if (array.length > 1) {
    // 2
    index = partition(array, left, right, compareFn); // 3
    if (left < index - 1) {
      // 4
      quick(array, left, index - 1, compareFn); // 5
    }
    if (index < right) {
      // 6
      quick(array, index, right, compareFn); // 7
    }
  }
  return array;
}

function quickSort(array, compareFn = defaultCompare) {
  return quick(array, 0, array.length - 1, compareFn);
}
// quickSort end
// quickSort end

// 二分查找 start
// 二分查找 start
const DOES_NOT_EXIST = -1;

function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0,
};

function binarySearch(array, value, compareFn = defaultCompare) {
  const sortedArray = quickSort(array);
  console.log("sortedArray:", sortedArray);

  let low = 0; // 2
  let high = sortedArray.length - 1; // 3

  while (low <= high) {
    // 4

    const mid = Math.floor((low + high) / 2); // 5
    console.log("mid", mid, "low:", low, "h：", high);

    const element = sortedArray[mid]; // 6
    // console.log('mid element is ' + element);

    if (compareFn(element, value) === Compare.LESS_THAN) {
      // 7
      low = mid + 1; // 8
      // console.log('low is ' + low);
    } else if (compareFn(element, value) === Compare.BIGGER_THAN) {
      // 9
      high = mid - 1; // 10
      // console.log('high is ' + high);
    } else {
      // console.log('found it');
      return mid; // 11
    }
  }

  return DOES_NOT_EXIST;
}

const array = [2, 3, 1, 5, 7, 9, 8];
console.log("二分查找结果：", binarySearch(array, 9));