二分查找-查找算法-数据结构与算法

迷南。 2022-02-12 12:23 270阅读 0赞

**介绍**  
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。  
但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列  
**查找过程**  
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；  
否则利用中间位置记录将表分成前、后两个子表，  
如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。  
重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

#include <iostream>
    
    using namespace std;
    
    int binarySearch(int *a,int start,int end,int findVal) //递归
    { 
    	if (a == NULL || start > end)
    		return -1;
    
    	int mid = start + (end - start) / 2;//(start + end) / 2;
    										/*使用(low+high)/2会有整数溢出的问题 （问题会出现在当low+high的结果大于表达式结果类型所能表示的最大值时， 这样，产生溢出后再/2是不会产生正确结果的，而low+((high-low)/2) 不存在这个问题*/
    	if (findVal == a[mid])
    		return mid;
    	else if (findVal < a[mid])
    		binarySearch(a, start, mid-1, findVal);//mid必须减1，不然进入无限循环
    	else if (findVal > a[mid])
    		binarySearch(a, mid+1, end, findVal);
    }
    
    int binarySearch1(int *a, int start, int end, int findVal)//循环
    { 
    	if (a == NULL || start > end)
    		return -1;
    	while (start <= end)
    	{ 
    		int mid = start + (end - start) / 2;//(start + end) / 2;
    											/*使用(low+high)/2会有整数溢出的问题 （问题会出现在当low+high的结果大于表达式结果类型所能表示的最大值时， 这样，产生溢出后再/2是不会产生正确结果的，而low+((high-low)/2) 不存在这个问题*/
    		if (findVal == a[mid])
    			return mid;
    		else if (findVal < a[mid])
    			end = mid-1;
    		else if (findVal > a[mid])
    			start = mid+1;
    	}
    	return -1;
    }
    
    int main()
    { 
    	int a[10] = {  1,2,3,5,12,12,12,15,29,55 };
    	int input = 0;
    	while(cin >> input)
    	{  
    		//cout << "findIndex: " << binarySearch(a, 0, sizeof(a)/sizeof(a[0])-1, input) << endl;
    		cout << "findIndex: " << binarySearch1(a, 0, sizeof(a) / sizeof(a[0]) - 1, input) << endl;
    	}
    	return 0;
    }