查找算法之二分法查找

基本的查找方法有遍历，也就是我们常人所理解的。一个一个去查询比较。

但这种方法比较耗时，成本较高，效率低下。

今天我们讲解一下二分法查找。

二分法查找的关键是，被查找的序列一定要是一个有序序列。

如果是无序的序列，那么二分法就失去意义了。

1、对序列进行拆分。按照对半原则，找到中间元素，然后设置为查找点 M。

2、对要查找的数据和这个查找点M的值比较，确定要查找的区域是左半边

还是右半边。

3、接着对需要查找的区域进行对半拆分，重复步骤1,2。直到不能拆分为止。

 

下面是code部分：

class BinaryFind{
	
	//注:我们在实现二分法(无论哪种查找方法)的时候，被查找的arr都是需要经过排序的
	//否则我们的查找没有意义，必须要一一遍历才可以。
	public void find(int leftIndex, int rightIndex, int val, int arr[])
	{
		//先找到中间元素的下标
		int midIndex = ((rightIndex + leftIndex) / 2);
		//然后找到这个下标对应的值，存放到minVal中
		int midVal = arr[midIndex];
		
		if(rightIndex >= leftIndex)  //防止陷入死循环
		{
			
			//当中间值大于要查找的值的时候，那么在左边半区查找
			if(midVal > val)
			{
				find(leftIndex, midIndex-1, val, arr);
			}
			else if(midVal < val)  //当midVal<val时在右边半区查找
			{
				find(midIndex+1, rightIndex, val, arr);
			}
			else if(midVal == val)//正好是midVal == val
			{
				System.out.println("val is find， Index is : " + midIndex);
			}
			
		}
		else
		{
			System.out.println("Not found your data!");
		}
	}
}

 

调用部分：

int arr[] = {1,32,45,79,82}; //这里一定要是经过排列的，有序的数列
		
		System.out.println("请输入要查找的数：");
		Scanner sr = new Scanner(System.in);
		int a = sr.nextInt();
		
		BinaryFind bf = new BinaryFind();
		bf.find(0, arr.length-1, a, arr);

 

查找结果：