二分查找

发表于   |   分类于   |  

二分查找算法是在有序数组中用到的较为频繁的一种算法，在未接触二分查找算法时，最通用的一种做法是，对数组进行遍历，跟每个元素进行比较，其时间为O(n).但二分查找算法则更优，因为其查找时间为O(lgn)，譬如数组{1， 2， 3， 4， 5， 6， 7， 8， 9}，查找元素6，用二分查找的算法执行的话，其顺序为：

  1. 第一步查找中间元素，即5，由于5<6，则6必然在5之后的数组元素中，那么就在{6， 7， 8， 9}中查找,
  2. 寻找{6， 7， 8， 9}的中位数，为7,7>6，则6应该在7左边的数组元素中，那么只剩下6，即找到了。

二分查找算法就是不断将数组进行对半分割，每次拿中间元素和goal进行比较。

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
26
27
28
29
30
31
32
33
int findTarget(int *array, int begin, int end, int target)
{
    while(begin <= end)
    {
    	int pMid = begin + (begin - end) / 2;
        if(array[pMid] == target)
        {
        	return pMid;
        }
        else if(array[pMid] > target)
        {
        	end = pMid - 1;
        }
        else
        {
        	begin = pMid + 1;
        }
    }
    return -1;
}
int main()
{
    int length, target;
    cin >> length;
    int array[1000];
    for(int i = 0; i < length; i++)
    {
    	cin >> array[i];
    }
    sort(array, length + array);
    cin >> target;
    cout << findlastTarget(array, 0, num - 1, target) << endl;
}

大家对于二分查找并不陌生，一般意义上的二分查找，往往返回给我们的是目标元素在排序数组中出现的一个随机的位置，但是在很多时候，我们却是需要目标元素的第一个和最后一个位置，才有意义。举个例子来说，我们要求得目标元素在排序数组中出现的次数，假如利用一般的方法，逐个比较目标元素和数组元素，时间复杂度O(n)，不能够令我们满意，既然数组是排序的我们很容易想到二分查找，在这里我们能不能使用二分查找的算法呢，答案是肯定的。只要我们能够利用二分查找找到目标元素出现的第一个和最后一个位置，就能够求得它出现的次数。我们如何来求得目标元素出现的第一个和最后一个位置呢，其实很简单，我们只需要对于二分查找的退出条件，做一个简单的设定就能得到我们理想的结果哦！
下面我们来看一下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int find1stTarget(int *array, int begin, int end, int target)
{
    while(begin < end)
    {
    	int pMid = (begin + end) / 2;
        if(array[pMid] < target)
        {
        	begin = pMid + 1;
        }
        else
        {
        	end = pMid;
        }
    }
    if(array[begin] == target)
    {
        return begin;
    }
    return -1;
}

在这里跟一般的二分查找的代码相比，仅仅是判断语句上做了一点细微的变化，序列是递增排列的，当中间值小于目标元素的时候，目标元素在序列的右边：begin = pMid + 1;其余的情况目标值在序列的左边：end = pMid；我们要查找的第一个目标元素的位置，一般的情况就是目标元素存在多个情况，由上述的两个判断条件，我们可以知道，如果查找到了目标元素，并且该目标元素不是第一个的时候，此时继续执行向左查找，而不终止，直到找到第一个元素为止。
同理，寻找最后一个元素也是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int findlastTarget(int *array, int begin, int end, int target)
{
    while(begin < end)
	{
        int pMid = (begin + end + 1) / 2; //保证取到中间靠后的位置
        if(array[pMid] > target)
		{
            end = pMid - 1;
        }
		else
		{
            begin = pMid;
        }
    }
    if(array[begin] == target)
    {
    	return begin;
	}
    return -1;
}

大家可以看出，跟我们取第一个元素时候的判断条件恰好相反，而两种情况处理的方式我们可以归结为以下两句话：

  1. 当我们要找到目标元素出现的第一个位置时候：当中间值大于等于目标元素的时候，我们要保留当前中间值的位置，并且在左边继续查找。
    这句话用条件语句表述就是：

    1
    2
    3
    4
    if(array[pMid] < target)
    {
    	begin = pMid + 1;
    }

  2. 当我们要找目标元素出现的最后一个位置的时候：当中间值小于等于目标元素的时候，我们要保留中间值的位置，并且在右边继续查找。

    1
    2
    3
    4
    if(array[pMid] > target)
    {
    	end = pMid - 1;
    }

同时注意为了取到稍后的元素,需要执行int pMid = (begin + end + 1) / 2;,保证取到中间靠后的位置.