算法基础：折半查找

太过爱你忘了你带给我的痛 2023-07-18 12:48 23阅读 0赞

##### 1. 题目描述 #####

对一个有序数组查找一个值key

##### 2. 考察知识点 #####

折半查找

##### 3. 思路 #####

1.  折半查找只能查找**有序**的线性表
2.  基本思路为：**每一次查找，将查找的区间从中间分为两部分，通过中间值判断要查找的值key可能在哪一部分，再次进行这样的查找**。
3.  可以使用递归的方法或while的方法

##### 4. 代码（Java） #####

参考网站: [link][].  
**递归实现：**

//输入参数 （原表，查找数字，要查找的表头，要查找的表尾）
    public static int Search(int[] arr,int key,int low,int high){
    		if(key < arr[low] || key > arr[high] || low > high){   //结束条件3种
    			return -1;				
    		}	
    		int mid = (low + high) / 2;                            //初始中间位置
    		if(arr[mid] > key){		                               //比关键字大则关键字在左区域                                        
    			return Search(arr, key, low, mid - 1);
    		}else if(arr[mid] < key){                              //比关键字小则关键字在右区域
    			return Search(arr, key, mid+ 1, high);
    		}else {
    			return mid;
    		}

**非递归实现：**

public static int Search(int[] arr,int key){
    		int low = 0;                                        //定义表头指针
    		int high = arr.length - 1;                          //定义表尾指针
    		int mid = 0;			                            //中间值定义mid	
    		if(key > arr[high] || low > high|| low > high){     //这三种情况下不可能有要查找的值
    			return -1;				
    		}	
    		while(low <= high){                                 //当表长度大等于1时结束查找
    			middle = (low + high) / 2;                      //取表中间的元素
    			if(arr[mid] > key){                             //若中间值比关键字大，则关键字在左区域
    				high = mid- 1;                              //查找左表
    			}else if(arr[mid] < key){                       //若中间值比关键字大，则关键字在左区域
    				low = mid+ 1;                               //查找右表
    			}else{
    				return mid;                                 //如果等于，直接返回mid  
    			}
    		}	
    		return -1;		                                   //表长度大等于1时仍然没有找到，说明表内没有此值，返回-1

##### 5. 时间及空间复杂度 #####

**时间复杂度**：O(log2 N)

**空间复杂度**：递归：O(log2N )，非递归：O(1)。

##### 6. 知识积累 #####

暂无

[link]: https://blog.csdn.net/maoyuanming0806/article/details/78176957