二分法递归查找 (递归分治篇)------- 算法笔记013

Dear 丶 2023-07-04 12:41 46阅读 0赞

### 问题引出 ###

> 给出我们一组数据：1 2 3 4 5 6 7 8 9 10  
> 要求返回要查找数据的下标

对于这样的一个问题我们可以有两种思路去解决；  
第一种：  
将这组数据存入一个数组当中，初始化一个下标，依次遍历数组的的元素，每次遍历的时候我们判断这个数组中的数据是否和我们要查找的数据相同，如果相同则返回这个数据所在数组的下标。如果全部遍历后还没有发现与其相同的数据，就返回-1.

int findNumber(int *arr,int e){ 
    		int inde=0;
    		for(index;index<arrSize;index++){ 
    			if(arr[index]==e){ 
    				return index;
    			}
    			
    		}
    		return -1;
    }

ok! 几行代码就搞定了。很简单啊，有什么难点吗？  
没错，要是在这10个数据之中找出某个数并返回它的下标确实没有什么难的，但是如果我们给的数据是1000个这样1-1000，或者是10000…这样的数据，我们每次全部遍历查找就太浪费时间了。这样就引出了我们的第二种解决思路。

二分法：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70]

public static int binarySearch(int [] Array,int value){ 
            int begin=0;//第一个索引值
            int end = Array.length-1;//最后一个索引值
            
            //当两个索引值相减大于1，也就是中间有数据的时候，进行循环
            while(end-begin>1){ 
                int middle=(begin+end)/2;	//中间数据的索引
                if(Array[middle]==value){ 
                    return middle;//当中间的数据正好等于要查找的数据 返回。
                }else if(value>Array[middle]){ 
                    begin=middle+1;
                    //如果要查找的数据大于中间的数据，那么说明要查找的数据一定在中间值的右边，所以将第一个索引值改为中间右边的索引值。继续查找。
                }else if(value<Array[middle]){ 
                    end=middle-1;
                    //同理将最后一个索引值改为中间左边的索引。
                }
            }
            //对特殊索引值的检验
            if(Array[begin]==value){ 
            	return begin;
    		}
    		
    		if(Array[end]==value){ 
    			return end;
    		}
            return -1;
        }

这里是用java写的一段，二分法查找的例子。为了方便我直接从某次作业中拷贝过来。  
先来分析这么一段二分查找算法，也是最普遍的二分算法。  
可以看出上面的函数是用循环迭代的方式来二分查找的。注意点是二分查找时数组里的元素必须是大小排列过后的。

下面我们来看一下二分查找的递归实现

int  findNumber(int data,int *arr,int first,int last){ 
    	int mid=(first+last)/2;//中间索引
    	int index=-1; //定义返回索引值
    	
    	if(arr[mid]==data){ 
    		return mid;//如果是则返回
    	}else if(data<arr[mid]){ 
    		last=mid-1;
    		index=findNumber(data,arr,first,last);//修改last调用自身
    	}else if(data>arr[mid]){ 
    		first=mid+1;
    		index=findNumber(data,arr,first,last);//修改first调用自身
    	}
    	
    	return index;
    
    } 
    假设要查找data值为9
    第一次：
    value: 1 2 3 4 5 6 7 8 9
    index: 0 1 2 3 4 5 6 7 8
    
    第二次：
    value: 6 7 8 9
    index: 5 6 7 8
    
    第三次：
    value:  8 9
    index:  7 8
    
    第四次：
    value:   9
    index:   8
    
    返回 8

可以看出只要我们将递归的条件设置好，底下就是一个不需要过多思考的过程，递归的魅力就在于此！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200211001931310.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz,size_16,color_FFFFFF,t_70