此文介绍了二分查找法

本文会随着作者日常学习进行补充及内容修正

  • N*2 =》N<<1
  • N*4 =》N<<2
  • N/2 =》N>>1
  • N*2+1 =》(N<<1)|1
  • +和-比>>和<<运算符优先级高
优先级 描述 运算符
1 括号 ()、[]
2 正负号 +、-
3 自增自减，非 ++、—、!
4 乘除，取余 *、/、%
5 加减 +、-
6 移位运算 <<、>>、>>>
7 大小关系 >、>=、<、<=
8 相等关系 ==、!=
9 按位与 &
10 按位异或 ^
11 按位或 \
12 逻辑与 &&
13 逻辑或 \ \
14 条件运算 ?:
15 赋值运算 =、+=、-=、*=、/=、%=
16 位赋值运算 &=、\ =、<<=、>>=、>>>=

1.找某个数是否存在

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static boolean exist(int[] arr,int num){
    if(arr == null || arr.length == 0){
        return false;
    }
    int mid=0;
    int L=0;
    int R=arr.length-1;
	while(L<R){
        mid=L+((R-L)>>1); //L+(R-L)/2
		if(arr[mid]==num){
            return true;
        }else if(arr[mid]>num){
            R=mid-1;
        }else{
            L=mid+1;
        }
    }
    return arr[L] == num;//相等返回true，否则返回false
}

2.找某个数的最左侧位置

例：112233445

查找>=2，最左则位置为第2个位置

  • 第一轮11223344

    mid = 7 / 2 = 3 即数字2

    2满足>=num的要求 R=3-1=2 ，即2 index=3

  • 第二轮112 23344

    mid =（2-0）/ 2 = 1 ，即数字1

    1不满足 >= num L=1+1=2

  • 第三轮 1 12 23344

    mid = (2- 2) / 2 = 0 ，即数字1

    1不满足 >= num 的要求

  • 最终返回index=3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int nearestIndex(int[] arr,int num){
    int L = 0;
    int R = arr.length - 1;
    int index = -1;
    while(L <= R){
        int mid = L + ((R - L) >> 1);
        if(arr[mid] >= num){
            index =mid;
            R = mid - 1;
        }else{
            L = mid + 1;
        }
    }
    return index;
}

3.局部最小值

例：134324

其中1、2为局部最小值,下面只返回一个局部最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static int getLessIndex(int[] arr){
        if(arr==null || arr.length==0){
            return -1;
        }
        if(arr[0]<arr[1]||arr.length==1){
            return 0;//第一位比第二位小
        }
        if(arr[arr.length-2]>arr[arr.length-1]){
            return arr.length-1; //第N位比倒数第N-1位小
        }
        int L=1;
        int mid=0;
        int R=arr.length-2;
        while(L<R){
            mid=L+((R-L)>>1);
            if(arr[mid]>arr[mid-1]){
                R=mid-1;
            }else if(arr[mid]>arr[mid+1]){
                L=mid+1;
            }else{
                return mid; // 前大后大
            }
        }
        return -2;
    }