二分查找及其变种

Posted on | Edited on

要点

  1. 每次查找范围一定要缩小，如果另mid = l 或 mid = r时，查找范围为长度为1时会陷入死循环。
  2. 如果写成 l < r , 当查找范围长度为1时，会导致找不到key。
  3. 写成mid = l + (r - l)/2，可防止整数溢出。
  4. 使用ans保存已经符合条件的最后的mid，最后返回即可。

查找符合条件的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int binary(int * arr, int val, int l, int r)
{
    if(arr == NULL || r < 0) return -1;
    int mid = 0;
    while(l <= r)
    {
        mid = l + (r - l)/2;
        if(arr[mid] == val)
        {
            return mid;
        }
        else if(arr[mid] > val)
        {
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    return -1;
}

查找符合要求的最小位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int binary(int * arr, int val, int l, int r)
{
    if(arr == NULL || r < 0) return -1;
    int mid = 0;
    int ans = -1;
    while( l <= r )
    {
        mid = l + (r - l)/2;
        if(arr[mid] >= val)
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    return ans;
}

查找符合要求的最大的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int binary(int * arr, int val, int l, int r)
{
    if(arr == NULL || r < 0) return -1;
    int mid = 0;
    int ans = -1;
    while(l <= r)
    {
        mid = l + (r - l)/2;
        if(arr[mid] <= val)
        {
            ans = mid;
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    return ans;
}