数组与链表

数组－时间复杂度 链表－时间复杂度
插 平均O(n)
涉及到元素挪动		 O(1)
删 平均O(n)
涉及到元素挪动		 O(1)
查 O(1) 平均O(n)

拓扑排序

对于有向无环图的节点进行按照访问顺序进行排序

Leetcode

二分查找

  1. public static int binarySearch(int[] nums,int target,int left, int right) {
  2.     //这里需要注意，循环条件
  3.     while (left <= right) {
  4.         //这里需要注意，计算mid
  5.         int mid = left + ((right - left) >> 1);
  6.         if (nums[mid] == target) {
  7.             return mid;
  8.         } else if (nums[mid] < target) {
  9.             //这里需要注意，移动左指针
  10.             left  = mid + 1;
  11.         } else if (nums[mid] > target) {
  12.             //这里需要注意，移动右指针
  13.             right = mid - 1;
  14.         }
  15.     }
  16.     //没有找到该元素，返回 -1
  17.     return -1;
  18. }

二分查找的思路及代码已经理解了，那么我们来看一下实现时容易出错的地方
1.计算 mid 时 ，不能使用 （left + right ）/ 2,否则有可能会导致溢出
2.while (left < = right) { } 注意括号内为 left <= right ,而不是 left < right ，我们继续回顾刚才的例子，如果我们设置条件为 left < right 则当我们执行到最后一步时，则我们的 left 和 right 重叠时，则会跳出循环，返回 -1，区间内不存在该元素，但是不是这样的，我们的 left 和 right 此时指向的就是我们的目标元素 ，但是此时 left = right 跳出循环
3.left = mid + 1,right = mid - 1 而不是 left = mid 和 right = mid。我们思考一下这种情况,见下图，当我们的target 元素为 16 时，然后我们此时 left = 7 ，right = 8，mid = left + (right - left) = 7 + (8-7) = 7，那如果设置 left = mid 的话，则会进入死循环，mid 值一直为7 。