欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

面试复习==华山论剑(一)?二分查找也是病:BSearch

程序员文章站 2024-01-23 15:03:28
...

看到一篇很有意思的文章就动手解决了一下问题。。。觉得有点意思~正逢毕业VS求职VS面试VS....高峰期,各种潮涌。

《编程珠玑》中的两句话:

  1. 尽管给了那么充裕的时间,只有大约10%的专业程序员能够写出正确的二分查找。
  2. 尽管第一个二分查找程序于1946年就公布了,但是第一个没有bug的二分查找程序在1962年才出现。

当时看到这的时候,我觉得有点夸张。这里不去讨论是否真的花了20年才人们才写出正确的代码,但这两句话至少告诉我们,不要小看二分搜索。

确实,写过bsearch的人都知道,迭代的出口很难在短时间内想清楚(反正我经常糊涂)。当然,常规的二分搜索大家现在基本都能写了,(写过这么多次,背也背下来了),但能写出来不代表真正理解了二分搜索。比如我们可以改动一下原型:从一个有序数组中找到大于x且最接近x的数。

说白了就是二分搜索,但是迭代的出口是什么的问题?

一、二分查找算法的原型JAVA代码表示

//传统二分搜索   PS:a数组中的值从小到大排列,找到目标X则返回下标值,未找到则返回-1 
	public static int bsearch(int[] a, int x) {
		int l=0,h=a.length -1 ;
		int m;
		while(h>=l) {
			m=(l+h)/2;
			if(a[m] ==x) {
				return m;
			} else if(a[m] <x){
				l=m+1 ;
			} else {
				h=m-1 ;
			}
		}
		System.out.println("l:"+l+" h:"+h);
		return -1 ;
	}

考虑一下要查找的元素不在序列中的情况:函数会返回-1,那l和h分别指向什么呢?

可以证明:l指向大于x的第一个元素,r指向小于x的第一个元素。(为什么?迭代的最后一步必然是l和h指向同一元素,然后为什么会变得比h大呢?想想就明白了)


二、变形1

//功能简介:  在有序数组中查找比x大但是最接近x的数
//二分搜索   PS:a数组中的值从小到大排列,找到目标X则返回下标值,未找到则返回-1 
	public static int bsearch_more(int[] a, int x) {
		int l=0,h=a.length -1 ;
		int m;
		while(h>=l) {
			m=(l+h)/2;
			if(a[m] ==x) {
				return (m+1)>a.length-1?-1:m+1;
			} else if(a[m] <x){
				l=m+1 ;
			} else {
				h=m-1 ;
			}
		}
		System.out.println("l:"+l+" h:"+h);
		return l ;
	}


三、变形2

//功能简介:  在有序数组中查找比x小但是最接近x的数
//二分搜索   PS:a数组中的值从小到大排列,找到目标X则返回下标值,未找到则返回-1 
		public static int bsearch_less(int[] a, int x) {
			int l=0,h=a.length -1 ;
			int m;
			while(h>=l) {
				m=(l+h)/2;
				if(a[m] ==x) {
					return (m-1)<0?-1:m-1;
				} else if(a[m] <x){
					l=m+1 ;
				} else {
					h=m-1 ;
				}
			}
			System.out.println("l:"+l+" h:"+h);
			return h ;
		}


附:主函数测试代码JAVA表示

public static void main(String[] args) {
		// TODO Auto-generated method stub
		//传统二分搜索
		int[] a = {1,4,7,9,10,17,20} ;
		int sign = bsearch(a,11) ;
		System.out.println(sign);
		sign = bsearch_more(a, 18) ;
		System.out.println(a[sign]);
		sign = bsearch_less(a, 5) ;
		System.out.println(a[sign]);
	}