算法--二分法

「爱情、让人受尽委屈。」 2022-12-25 10:55 119阅读 0赞

## 一、思想 ##

假设待查找序列和题目的要求之间的关系是单调递增的，先取区间的中心，判断该处函数值和题目标准值的大小关系，如果函数值偏小，那么应该在中心右侧的区间继续查找；如果函数值偏大 ，那么应该在中心左侧区间继续查找，直到找到对应的值或者区间缩小到左右端点之间不再包含其他数据结束。

（1）首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束，否则执行下一步。

（2）如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤（1）的操作。

（3）如果某一步数组为空，则表示找不到目标元素。

## 二、使用条件 ##

（1）待查找的序列区间单调有序（单调递增或单调递减都可以）；

（2）待查找序列和题目的要求建立的函数关系单调有序；

## 三、示例代码 ##

/** @function      dichotomy_find_table_from_max
    	* @brief         二分查找算法,表中数据从大到小 
    	* @param:     	 table: 表地址；
    	* @param: 			 tableSize: 表长度;
    	* @param: 				data: 要查找的数据
    	* @return        -1:出现异常； 其他：数据在表中的位置
    	*/
    s8_t dichotomy_find_table_from_max(const s32_t* table, u8_t tableSize, s32_t data)  
    {  
    	s8_t  pos = 0;
    	u8_t head,end;  
    	u8_t i;  
    
    	if(table == NULL)           return -1;
    	if(0 == tableSize)					return -1;
    	if(1 == tableSize)          return 0;
    	
    	head = 0;  
    	end = tableSize-1 ;  
    	i = 0; 
    	
    	if(data >= table[head]) 			
    	{
    		return head ;  
    	}
    	else if(data <= table[end])   
    	{
    		return end ; 
    	}
    	
    	while(head < end)  
    	{  
    		pos = (head+end)/2;  
    
    		if(data == table[pos]) 				break;  
    		if((data<table[pos]) && (data>table[pos+1])) break;  
    			
    		/* 区分是上半区还是下半区 */
    		if(data > table[pos])  end = pos ;  /* 上半区 */                    
    		else head = pos ;     /* 下半区 */
    			
    		if(i++ > tableSize) break ;  
    	}  
    
    	if(head > end ) return -1;   
    
    	return pos ;  
    }  
      
      
    
    /** @function      dichotomy_find_table_from_max
    	* @brief         二分查找算法,表中数据从小到大 
    	* @param:     	 table: 表地址；
    	* @param: 			 tableSize: 表长度;
    	* @param: 				data: 要查找的数据
    	* @return        -1:出现异常； 其他：数据在表中的位置
    	*/
    s8_t dichotomy_find_table_from_min(const s32_t* table, u8_t tableSize, s32_t data)
    {  
    	s8_t  pos = 0;
    	u8_t head,end;  
    	u8_t i;  
    
    	if(table == NULL)           return -1;
    	if(0 == tableSize)					return -1;
    	if(1 == tableSize)          return 0;
    	
    	head = 0;  
    	end = tableSize-1 ;  
    	i = 0;  
    
    	if(data >= table[end]) 				return end ;  
    	else if(data <= table[head])  return head;  
    
    	while(head < end)  
    	{  
    		pos = (head+end)/2 ;  
    
    		if(data == table[pos] ) 			break;  
    		if((data<table[pos+1]) && (data>table[pos])) break;  			
    			
    		/* 区分是上半区还是下半区 */
    		if(data > table[pos]) head = pos ;  //end = m ;                    
    		else end = pos ;//head = m ;   
    			
    		if(i++ > tableSize) break ;  
    	}  
    
    	if(head > end ) return -1;   
    
    	return pos ;  
    }