二分法及其变种

[OPY-bbt]

No description provided.

[OPY-bbt]

循环

const mock_data = [1, 2, 3, 5, 9];

function bsearch(array, value) {
  let low = 0;
  let high = array.length - 1;

  while(low <= high) {
    let mid = Math.floor((low + high) / 2);

    if (array[mid] === value) {
      return mid;
    } else if (array[mid] > value) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }

  return -1;
}

document.body.innerHTML = bsearch(mock_data, 1);

[OPY-bbt]

递归

const mock_data = [1, 2, 3, 5, 9];

function bsearchRecursion (array, value) {
  return bsearchRecursionInternally(array, value, 0, array.length - 1);
}

function bsearchRecursionInternally(array, value, low, high) {

  if (low > high) return -1;

  let mid = Math.floor((low + high) / 2);

  if (array[mid] === value) {
    return mid;
  } else if (array[mid] > value){
    return bsearchRecursionInternally(array, value, low, mid - 1);
  } else {
    return bsearchRecursionInternally(array, value, mid + 1, high);
  }
}
 
document.body.innerHTML = bsearchRecursion(mock_data, 9);

[OPY-bbt]

二分法求一个数的平方根，精确到小数点后六位

function squareRoot(value) {
  let low = 0;
  let high = value;
  let mid = (low + high) / 2;

  while(Math.abs(mid * mid - value) >= 1e-6 ) {
    mid = (low + high) / 2;
    if (mid * mid > value) {
      high = mid;
    } else if (mid * mid < value) {
      low = mid;
    }
  }
  return mid.toFixed(6);
}

document.body.innerHTML = squareRoot(10);

[OPY-bbt]

二分法变体

const mock_data = [1, 1, 2, 2, 3, 4, 9, 9];

// 变体一： 查找第一个值等于给定值的元素
function bsearch1(array, value) {
  let low = 0;
  let high = array.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);

    if (array[mid] > value) {
      high = mid - 1;
    } else if (array[mid] < value) {
      low = mid + 1;
    } else {
      // 相等的情况，再看前面的值是否相等，如果相等调节high;
      if (mid > 0 && array[mid - 1] === value) {
        high = mid - 1;
      } else {
        return mid;
      }
    }
  }

  return -1;
}

// 变体二： 查找最后一个值等于给定植的元素
function bsearch2(array, value) {
  let low = 0;
  let high = array.length - 1;

  while(low <= high) {
    let mid = Math.floor((low + high) / 2);

    if (array[mid] > value) {
      high = mid - 1;
    } else if (array[mid] < value) {
      low = mid + 1;
    } else {
      if (mid < array.length - 1 && array[mid + 1] === value) {
        low = mid + 1;
      } else {
        return mid;
      }
    }
  }

  return -1;
}

// 变体三： 查找第一个大于等于给定值的元素
function bsearch3(array, value) {
  let low = 0;
  let high = array.length - 1;

  while(low <= high) {
    let mid = Math.floor((low + high) / 2);

    if (array[mid] >= value) {
      if (mid === 0 || array[mid - 1] < value) {
        return mid;
      }
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }

  return -1;
}

// 变体四： 查找最后一个小于等于给给定值的元素
function bsearch4(array, value) {
  let low = 0;
  let high = array.length - 1;

  while(low <= high) {
    let mid = Math.floor((low + high) / 2);

    if (array[mid] <= value) {
      if (mid === array.length - 1 || array[mid + 1] > value) {
        return mid;
      }

      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
}

document.body.innerHTML = bsearch4(mock_data, 1);