透过大脑思考的：二分查找

经过大脑思考的：二分查找

首先声明：这是一个经过同学分析的、老师要求的、自己脑袋思考的、打过草稿的、用圆珠笔，右手亲手写的java有关的二分查找。

什么是二分查找：以一个数组（已经升序排列好了的）来分析，首先找到整个数组索引值的中间点的数组的key，如果等于你所要找的值X则这个索引值就是你要找的；如果>X，证明素要找的的前半部分，否则在后半部分，然后递归即可。（当然，这是我个人的理解）

我的代码实现：

//我以一个int数组 找一个int x为例
	static int low,high;//low是第一个索引值，high是最后一个索引值
	int arr[]=new int[Len]; //Len已知
	low=0;high=Len-1;//一开始给他们赋初值
	public int fun(int x){
		int mid=(low+high)/2;//将索引的中间值赋给mid
		if(low>=high){//最小索引都大于最大的了肯定就是没找到了
			return -1;
		}else if(arr[mid]==x){//刚好找到
			return mid;	
		}else if(arr[mid]>x){//左半部分
			high=mid-1;
			return fun(x);
		}else if(arr[mid]<x){
			low=mid+1;
			return fun(x);
		}
		return -1;
	}

他人理解：首先将待查值K与有序表array[0]到array[n-1]的中点mid上的关键字array[mid].key进行比较，若相等，则查找成功；否则，若array[mid].key>k ，则在array[1]到array[mid-1]中继续查找，若有array[mid].key<k ，则在array[mid+1]到array[n-1]中继续查找。每通过一次关键字的比较，区间的长度就缩小一半，区间的个数就增加一倍，如此不断进行下去，直到找到关键字为K的元素；若当前的查找区间为空(表示查找失败)。（比较专业）

int    bin_search (NODE array[ ],int n,int k)
{ int low=0,hig=n-1,mid;
 while(low<=hig)
   { mid=(low +hig)/2;                           //取区间中点
     if (array[mid].key= =k) return(mid);      //查找成功
     if (array[mid].key>k)
         hig=mid-1;                                   //在左子区间中查找
           else  low=mid+1;  }                     //在右子区间中查找
          return(-1); }                                         //查找失败

感觉还是自己写的自己理解容易些，多亏了志桢和国栋耐心的修改哈！虽然之前就看过二分查找，也大致了解二分的思想，但到底还是不动手不知道这个有多难啊！！！

透过大脑思考的：二分查找

相关推荐