二分查找的大致了解

数据结构笔记

1.斐波那契函数
除去前几个特例，后面的数均为前一个数+后面一个数
public static long Fib(int N){
if(N < 3){
return 1;
}else{
return Fib(N-1) + Fib(N-2);
}
}

2.复杂度只说最坏情况下。

3.1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

4.二分查找中间索引为向下取整：3.5取3。

5. java中的小数计算会自动取整。（1+2）/2=1;但数太大时最高位会变成符号位即突破正整数限制变为以负号开头的数字。这个时候就开始使用右移运算符>>>,即在二进制层面右移一位来代替除号÷的弊端。

6. 二分查找核心循环，左闭右开区间 [left, right)。

7.如果right=a.length ;则代表右侧指针不进行数据比对，只用来进行缩小边界，此时while(1<right-left)。
8.数组采用二分查找中间项是数组的中间序列号，要生成一个临时变量将数组中间序列号所代表的值赋给它，例如：int midVal = a[mid]; 之后才能进行后续比较。

9.java中的绝对值函数：Math.abs()。

10. 数组复制函数：System.arraycopy（旧数组，起始位置，目标数组，插入点的起始位置，原数组复制到新数组的长度（例如旧数组为：123，复制的长度为2，根据数组下标应该复制数组下标1之前的内容1和2））。

11.找最左边第一个目标数，缩右边界，因为对象数组本身已经就是从右到左的从小到大的有序数组，缩右边界，就是要排除左边是否还有目标数；
反之找最右边第一个目标数则缩左边界。

12.二分查找的通用公式：
class Solution{
public int search( int[ ] nums, int target){
int left = 0;
int right = nums.length-1;
while(left <= right){
int mid = left+(left + right)/2;
int midval = nums[mid];
if( target==midval){
return mid;
}
if(target<midval){
right = mid -1; //核心操作是通过 target 满足条件来操控一边的指针一直移动，另一边不动直到不满足while的()中的前提条件，从而跳出循环
}else{
left =mid +1;
}

}
return -1;
}
}

13.Leftmost: 找靠左返左， 改动原始二分查找代码：return -1; 改为 return left; 意味返回值为>=target的***最靠左的索引***。

14.Rightmost:找靠右返右， 改动原始二分查找代码：return -1; 改为 return left -1；或 return right; 意味返回值为<=target的***最靠右的索引*** 。

15.求排名: Leftmost(target) =target的索引 + 1 。

16求前任：Leftmost(target) =target的索引 - 1 。

17.求后任：Rightmost(target) = target的索引 +1 。