首页 > 笔试面试题, 算法 数据结构 > 二分查找,你真的会吗?

二分查找,你真的会吗?

2012年10月6日 发表评论 阅读评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

面试常让写二分查找或其扩展的程序,以前总觉得很简单,但是真动手写起来,细节很多,容易出错的地方也很多,真是秒杀眼高手低的利器,本节就二分查找以及相关扩展程序都实现一下,同时将可能出错的地方以及需要注意的细节也一并说明,水平有限,欢迎补充。

内容如下:

1)二分查找元素key的下标,如无 return -1

2)二分查找返回key(可能有重复)第一次出现的下标,如无return -1

3)二分查找返回key(可能有重复)最后一次出现的下标,如无return -1

4)二分查找返回刚好小于key的元素下标,如无return -1

5)二分查找返回刚好大于key的元素下标,如无return -1

注:以上所有问题可能出错的地方以及需要注意的细节说明在代码注释中。

直接上代码:

/* binsearch 寻找key下标,不存在 return -1 */

/* binsearch 注意点【找不到 vs 死循环】
 * 1. left <= right 如改为 left < right 可能找不到key
 *    例如 1 2 3 4 5;key=5; left==right时候才搜到key
 * 2. left = mid + 1;
 *    如上left改为=mid,可能死循环,例如上面例子,
 *    当left指向4时候,right指向5,此时,死循环;
 *    死循环的根本原因在于left,当两个指针left与right相邻
 *    left可能永远等于mid,而right不会因为等于mid死循环
 */
int binsearch(int * arr, int lef, int rig, int key)
{
	if(!arr)	return -1;
	int left = lef, right = rig;
	while(left <= right)
	{
		int mid = left + ((right-left)>>1);
		if(arr[mid] < key)
		{
			left = mid + 1;
		}else if(arr[mid] > key)
		{
			right = mid - 1;
		}else
			return mid;
	}
	return -1;
}

/* binsearch_min 返回key(可能有重复)第一次出现的下标,如无return -1
 *
 * binsearch_min 注意点【死循环】
 * 1. 如果while(left < right)改为(left <= right)可能死循环;
 * 2. 循环结束条件,left == right
 *
 * 该代码我测试了很多用例,没发现反例,我认为是对的
 * 但网上都是用的left<right-1的条件并分别对arr[left]和arr[right]
 * 进行检查;我认为我写的更简练,希望有兴趣的读者帮忙review这段代码
 * 如发现反例指出错误,感激不尽,嘿
 */
int binsearch_min(int * arr, int lef, int rig, int key)
{
	if(!arr)	return -1;
	int left = lef, right = rig;
	while(left < right)
	{
		int mid = left + ((right-left)>>1);
		if(arr[mid] < key)
		{
			left = mid+1;
		}else
		{
			right = mid;
		}
	}
	if(arr[left] == key)	return left;
	return -1;
}

/* binsearch_max 返回key(可能有重复)最后一次出现的下标,如无return -1
 *
 * binsearch_max 注意点【死循环 vs 越过目标位置】
 * 1. 如果改为while(left < right)可能死循环;
 * 2. 如果left=mid改为left=mid+1;则有可能越过目标位置
 * 3. 循环结束条件,left == right || left == right -1
 *
 * 如非要死记:找最大的等号放<=key的位置,找最小的等号放>=key位置
 */
int binsearch_max(int * arr, int lef, int rig, int key)
{
	if(!arr)	return -1;
	int left = lef, right = rig;
	while(left < right -1)
	{
		int mid = left + ((right-left)>>1);
		if(arr[mid] <= key)
		{
			left = mid;
		}else
		{
			right = mid;
		}
	}
	if(arr[right] == key) // 找max,先判断right
	{
		return right;
	}else if(arr[left] == key)
	{
		return left;
	}else
		return -1;
}

/* binsearch_justsmall 返回刚好小于key的元素下标,如无return -1
 *
 * binsearch_justsmall 注意点【死循环 vs 越过目标位置】
 * 1. 如果改为while(left < right)可能死循环;因为left=mid的缘故
 * 2. 如果left=mid改为left=mid+1;则有可能越过目标位置
 * 3. 循环结束条件,left == right || left == right -1
 */
int binsearch_justsmall(int * arr, int lef, int rig, int key)
{
	if(!arr)	return -1;
	int left = lef, right = rig;
	while(left < right - 1)
	{
		int mid = left + ((right-left)>>1);
		if(arr[mid] < key)
		{
			left = mid;
		}else
		{
			right = mid - 1;
		}
	}
	if(arr[right] < key) // 找刚好小于,先判断right
	{
		return right;
	}else if(arr[left] < key)
	{
		return left;
	}else
		return -1;
}

/* binsearch_justgreat 返回刚好大于key的元素下标,如无return -1
 *
 * binsearch_justgreat 注意点【死循环 vs 检查元素是否大于key】
 * 1. 如果改为while(left <= right)可能死循环;因为right = mid;
 * 2. 最后注意检查arr[right]是否大于key
 * 3. 循环结束条件,left == right
 */
int binsearch_justgreat(int * arr, int lef, int rig, int key)
{
	if(!arr)	return -1;
	int left = lef, right = rig;
	while(left < right)
	{
		int mid = left + ((right-left)>>1);
		if(arr[mid] <= key)
		{
			left = mid + 1;
		}else
		{
			right = mid;
		}
	}
	if(arr[right] > key)	return right;
	return -1;
}

测试程序,输入测试用例个数testcase,程序随机生成testcase个数组,并随机生成key,对以上函数进行测试。代码如下:

#define N 20  // 测试数组大小

void outputarr(int * arr, int len)
{
	for(int i = 0; i < len; ++i)
		printf("%d ", arr[i]);
	printf("\n");
}

void main()
{
	int testcase = 0;
	scanf("%d", &testcase);
	int * arr = new int [N];

	srand(1); // 设置随机种子

	while(testcase--)
	{
		for(int i = 0; i < N; ++i)  // 随机生成数组
		{
			arr[i] = rand() % (N);
		}
		int key = rand() % (N);
		outputarr(arr,N);
		std::sort(arr,arr+N);      // 排序
		outputarr(arr,N);

		printf("binsearch:           key-%d %d\n", key, binsearch(arr,0,N-1,key));
		printf("binsearch_min:       key-%d %d\n", key, binsearch_min(arr,0,N-1,key));
		printf("binsearch_max:       key-%d %d\n", key, binsearch_max(arr,0,N-1,key));
		printf("binsearch_justsmall: key-%d %d\n", key, binsearch_justsmall(arr,0,N-1,key));
		printf("binsearch_justgreat: key-%d %d\n", key, binsearch_justgreat(arr,0,N-1,key));
	}

	delete [] arr;
}

一次运行结果如图:

如有误,欢迎指正讨论。

本文相关代码可以到这里下载。

(全文完)

  • http://zhangnew.com zhangnew

    博主真乃神人也,在 lintcode 测试通过,多谢。

  • yel huang

    半夜不知怎么回事,看到你的博客,乱乱的,随手写了一个返回第一个下标的二分查找:和普通的二分查找就改变了一行。
    int lo = 0;
    int hi = nums.length;
    int result = -1;
    while (lo <= hi) {
    int mid = (hi - lo) / 2 + lo;
    if (nums[mid] target)
    hi = mid - 1;
    else {
    result = mid;
    hi = mid - 1;// 普通版:这里return result 改为 hi = mid - 1继续找最佳结果,不谢~
    }
    }
    return result;

  • Cholerae Hu

    如果求最大一个 不大于目标 的数该怎么搞?就是最大一个小于等于目标的数。好像很难优雅地实现

    • Yx.Ac

      可以这样理解:求目标key,如果没有,返回刚好小于它的那个数对吧?
      其实文中的二分写的不够好,一直没有修改,这里说一下,有一种比较通用的方法,无论上面那种情况,while循环条件都使用 start+1<end即可,最后同时判断start和end:

      while(start + 1 &lt; end)
      {
          mid = start + (end - start) / 2;
          if(arr[mid] == key)
              start = mid;
          else if(arr[mid] &gt; key)
              end = mid;
          else if(arr[mid] &lt; key)
              start = mid;
      }
      if(arr[start] &lt;= key)
          return arr[start];
      if(arr[end] &lt;= key)
          return arr[end];
      return -1;
      

      请注意:这里的退出条件一定是start+1==end
      不知这个回答你没有 :-) 我想是对的,哈哈

  • Donkey

    对于2和3这两个问题,如下解法是不是和1的思路更一致,更好理解一些?(以2为例,3的解法和2是大同小异的)

    int binsearch_min1(int * arr, int lef, int rig, int key)
    {
    if(!arr) return -1;
    int ret = -1, left = lef, right = rig;

    while(left >1);
    if(arr[mid] key)
    {
    right = mid-1;
    }
    else
    {
    ret = mid; /* 记录一下已经找到的位置,初始值为-1*/
    right = mid - 1; /* 对问题3而言,此处应该是:left = mid + 1;*/
    }
    }
    return (ret);
    }

  • http://oct-man.blogspot.com Tsung1990

    见我的博客文章(被墙)吧,代码显示好像有问题。@Tsung1990

    • Yx.Ac

      好的,谢谢!

  • http://oct-man.blogspot.com Tsung1990

    我想你的程序是没有错误的,不过描述起来感觉在写的过程中得一定的技巧才可以写好,但实际上面试过程中这挺难的。特别是你说的left,right的设置和循环条件。我想一个更简单的方法是使用循环不变式,这里举个例子:

    存在就返回最后一个相等的位置,否则返回-1。

    返回最后一个相等的位置:此时循环不变式可以表示为“[0, left)所有元素小于等于val,而(right, N-1]所有元素都大于val”。注意初始化的时候left=0, right = N-1,显然是满足条件的(因为两个都是空集);在循环的过程中我们只需要保证始终维护这个不变式的正确性就可以了。这样当程序终止的时候我们`arr[right]`就是第一个小于等于val的元素了。程序如下(我目前的测试没有问题,欢迎交流):
    int upperBound(std::vector& arr, int val) {
    int left = 0, right = arr.size() - 1;
    while (left val) right = mid - 1;
    else left = mid + 1;
    }
    if (right >= 0 && arr[right] == val) return right;
    return -1;
    }

    • Yx.Ac

      抱歉回复这么晚~~ 俺找时间拜读下大侠博客,哈哈

  • Eillen

    对于第2和第3个题目
    1)找第一次出现的位置,mid位置的元素如果= key, 这high = mid;
    2)找最后一次出现的位置,mid位置的元素如果 > key 则 high = mid - 1; mid的元素如果 <= key, 这low = mid;

    • Yx.Ac

      @Eillen 这里是要说明什么?另一种程序写法?

  • Eillen

    其实对于最后面两个题目,寻找最后一个小于key和第一个大于key的元素。
    我是这样思考的,用二分查找去找key
    1)如果key存在的话,那么key的左边是最后一个小于key的元素(这时要注意防止key是第一个元素,就不存在最后一个小于key的元素了)。key的右边是最后一个大于key的元素(这时要注意防止key是最后一个元素,就不逊在第一个大于key的元素了);
    2)key不存在的话,使用的low和high指针就会变成low > high,如果high和low都没有越界,这hign指向的就是最后一个小于key的元素,low指向的就是第一个大于key的元素;如果high越界,那就没有最有一个小于key的元素;如果low越界,这没有第一个大于key的元素

    • Yx.Ac

      @Eillen 恩,这样也是对的,哈

  • tong

    问下楼主几年级?挺厉害的

  • http://www.thehtmlcoders.com/ TheHTMLCoders

    just wanted to write thank you :) loved your article.

  • http://mazheng.org 冰上游鱼

    的确啊,二分查找挺难写对的。我写二分经常因为left,right界的变化不正确而陷入死循环。

    • Yx.Ac

      哈,是这样啊,对于不同的变化,细节还是比较多的。@冰上游鱼

  • http://www.tz15.com 团长

    现在会了

    • Yx.Ac

      :-)