二分查找

给定一个从小到大的有序数组，查找元素k是否在数组中。
简单的思路是顺序查找，从前往后，逐个对比，但是效率较低。
可以根据数组从小到大有序这一特点来进行折半查找（二分查找）。

二分查找实现

可以使用left和right来表示当前要查找的区间左右边界。显然，初始化left = 1, right = n。

  • 取出中间元素mid = (left + right) / 2
  • 比较a[mid] 和 k的大小关系
    • a[mid] > k，答案在左边区间，修改right = mid - 1
    • a[mid] < k，答案在右边区间，修改left = mid + 1
    • a[mid] == k，找到答案，输出相应信息
  • 在left <= right的情况下，执行上述操作，否则查找失败。

参考程序

  1. int binarySearch (int k, int l, int r) {
  2.     int mid;
  3.     while (l <= r) {
  4.         mid = l + r >> 1;
  5.         if (a[mid] < k) l = mid + 1;
  6.         else if (a[mid] > k) r = mid - 1;
  7.         else return mid;
  8.     }
  9.     return -1; //未找到
  10. }

a4dcc407efe745909fc97b91b76df63d.gif
冒泡排序

        let kong = 0
      // 利用冒泡排序将新数组进行排序
      for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
          if (arr[j] > arr[j + 1]) {
            kong = arr[j]
            arr[j] = arr[j + 1]
            arr[j + 1] = kong
          }
        }
      }