常用算法
二分查找：
只能是有序的数组，而且应该用在插入删除不频繁的场景中。
public static int commonBinarySearch(int[] arr,int key){
int low = 0;
int high = arr.length - 1;
if(key < arr[low] || key > arr[high] || low > high){
return -1;
}
while(low <= high){
int middle = low+((high-low)>>1);//这种写法性能最优 // low+(high-low)/2; //(low + high) / 2 这种写法可能会造成溢出
if(arr[middle] > key){
//比关键字大则关键字在左区域
high = middle - 1;
}else if(arr[middle] < key){
//比关键字小则关键字在右区域
low = middle + 1;
}else{
return middle;
}
}
return -1; //最后仍然没有找到，则返回-1
}
递归的二分查找
public static int bsearch(int[] arr,int key){
return recursionBinarySearch(arr,key,0,arr.length-1);
}
public static int recursionBinarySearch(int[] arr,int key,int low,int high){
if(key < arr[low] || key > arr[high] || low > high){
return -1;
}
int middle = (low + high) / 2; //初始中间位置
if(arr[middle] > key){
//比关键字大则关键字在左区域
return recursionBinarySearch(arr, key, low, middle - 1);
}else if(arr[middle] < key){
//比关键字小则关键字在右区域
return recursionBinarySearch(arr, key, middle + 1, high);
}else {
return middle;
}
}
二分查找（重复数据）
查找第一个值等于给定的元素
public static int bserach1(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;
}
二分查找 （重复）
查找第一个值大于给定的元素
public static int bserach2(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){
if((mid==0)||(a[mid-1]<value)){return mid;}
else high = mid -1;
}else {
low= mid +1;
}
}
return -1;
}
跳表我们通过索引层结点的 down 指针，下降到原始链表这一层，继续遍历。
第 k级索引结点的个数就是 n/(2k次方)。
整个链表高度是log2n。
如果每一层都要遍历 m 个结点，那在跳表中查询一个数据的时间复杂度就是 O(m*logn)。
可知m=3。
所以时间复杂度是O(logn)（时间换空间）
空间复杂度是O(n)(n/2+n/4+n/8…+8+4+2=n-2)
但是在实际的软件开发中，原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值和几个指针，并不需要存储对象，所以当对象比索引结点大很多时，那索引占用的额外空间就可以忽略了。
跳表的插入、删除（时间复杂度也是 O(logn)
插入
如果插入的数据过多，很有可能会退化成单链表，所以我们需要动态的更新索引。
可通过一个随机函数，生成一个K值，K值是第几层就在第几层添加该元素的索引。
删除跳表结点
如果这个结点在索引中也有出现，我们除了要删除原始链表中的结点，还要删除索引中的。
Redis 中的有序集合是通过跳表来实现的（其实是复合数据结构）（应该是由一个双hashmap构成的字典和跳跃表实现的）
插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。
但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。
对于按照区间查找数据这个操作，跳表可以做到 O(logn)的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。这样做非常高效。
跳表更加灵活，它可以通过改变索引构建策略，有效平衡执行效率和内存消耗。