简述

二分查找（Binary Search）是一种针对有序数据集合的查找算法。

跳表（Skip List）是一种优秀的动态数据结构，支持快速的插入、删除、查找操作。

二分查找（Binary Search）

原理：通过每次跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到待查找元素，或者区间被缩小为0。

时间复杂度：O(logn)。

最简单的二分：

//二分查找的普通实现(简单版)
public int bsearch(int[] a, int n, int value){
	int low = 0;
	int high = n - 1;
	while(low <= high){
		int mid = (low + high) /2;
		if(a[mid] == value){
			return mid;
		} else if(a[mid] < value){
			low = mid + 1;
		} else {
			high = mid -1;
		}
	}
	return -1;
}
//二分查找的递归实现
public int bsearch(int[] a, int high,int low, int value){
	if(low > high) return -1;
	int mid = low + ((high - low) >> 1);
	if(a[mid] == value)
		return mid;
	else if(a[mid] < value)
		bsearch(a,high,mid + 1,value);
	else
		bsearch(a,high - 1,mid,value);
}

要点：

循环退出条件，是low <= high，而不是low < high;
mid的取值通常为(low+high)/2，但是可以写为low+(high-low)/2，为了提高效率，除以2可以写为右移一位，即low+((high-low)>>1);
low和high的下标要常更新。

局限性：依赖顺序表结构；数据必须是有序的；数据量很小时时间和顺序遍历差别不大；数据量太大时数组连续内存可能不够。

变种1：查找第一个值等于给定值的元素（提示：判断下标是否等于0，或者某下标的前一节点是否等于给定值）。
参考代码：

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == 0) || (a[mid - 1] != value)) return mid;
      else high = mid - 1;
    }
  }
  return -1;
}

变种2：查找最后一个值等于给定值的元素（提示：判断下标是否等于0，或者某下标的后一节点是否等于给定值）。

变种3：查找第一个子节点大于等于给定值的元素（提示某下标的前一节点是否小于给定值）。

变种4：查找最后一个小于等于给定值得元素（提示：某下标的后一节点是否大于给定值）。

二分查找总结

一般情况下，凡是可以用二分查找解决的，绝大部分都倾向于使用散列表或者二叉查找树，即使二分查找在内存使用上更节省。但是一般对于近似查找，二分查找的优势比较明显。

跳表（Skip list）

原理：对要查找的数据进行索引操作，一般情况下，两个节点中间都会有一个索引节点；
时间复杂度：O(logn)
空间复杂度：O(n)

两个节点中间都有一个节点则第一层索引有n/2个节点；第二层有n/4个节点，k级有n/(2^k)……假设索引有h级，最高级有2个节点，则n/2^h=2，从而求得h=log2n - 1,如果包含原始链表，则h = log2n,如果每一层都要遍历m个节点，则跳表中查询一个数据的时间复杂度是(m logn)，再加上每一层需要遍历的节点不超过3个节点，所以算出时间复杂度是O(logn)。

动态插入和删除：
主要时间耗费在插入位置的查找上，所以是O(logn)。

跳表索引动态更新：
插入数据时，根据随机函数，来决定将这个节点插入到哪几级索引中，以此来维护索引平衡性，不至于使得两个索引节点之间包含大量节点。

参考

本节相关的学习代码参考github：

https://github.com/liuhuijun11832/algorithm