/**
 * 二叉树搜索
 */

var arr = [5, 8, 10, 3, 1, 6, 9, 7, 2, 0, 4];

function search(searchValue) {
  var index = 0;

  var root = {
    index: index,
    value: arr[index],
  };

  index += 1;

  while (index < arr.length) {
    var val = arr[index];

    var node = root;

    while (node) {
      if (val < node.value) {
        if (!node.left) {
          node.left = {
            index: index,
            value: val,
          };
          break;
        }
        node = node.left;
      } else {
        if (!node.right) {
          node.right = {
            index: index,
            value: val,
          };
          break;
        }
        node = node.right;
      }
    }

    index++;
  }

  var currentNode = root;

  while (currentNode) {
    if (currentNode.value === searchValue) {
      return currentNode.index;
    }

    if (searchValue > currentNode.value) {
      currentNode = currentNode.right;
    } else {
      currentNode = currentNode.left;
    }
  }

  return -1;
}

for (const el of arr) {
  console.log(`search(${el}) = ${search(el)}`);
}

/**
 * 二分法搜索
 */

var arr = new Array(20).fill(1).map((_, index) => index + 8);

function search(searchValue) {
  var startIndex = 0;
  var endIndex = arr.length - 1;

  var compare = () => {
    var middleIndex = Math.floor((startIndex + endIndex) / 2);
    var val = arr[middleIndex];

    if (val === searchValue) {
      return middleIndex;
    }

    if (middleIndex < 0 || startIndex > endIndex) return -1;

    if (val > searchValue) {
      endIndex = middleIndex - 1;
      return compare();
    } else {
      startIndex = middleIndex + 1;
      return compare();
    }
  };

  return compare();
}

for (const el of arr) {
  console.log(`search(${el}) = ${search(el)}`);
}