检索算法——顺序查找与二分查找

检索算法——顺序查找与二分查找 2023-03-22 586

1.问题

在一个排好序的数组T[1…n]中查找x，如果x在T中，输出x在T的下标j；如果x不在T中，输出j=0。

2.解析

顺序查找算法原理：对于任意一个序列T以及一个给定的元素x，将给定元素x与序列T中元素依次比较，直到找出与给定关键字x相同的元素，或者将序列T中的元素与其都比较完为止。

顺序查找算法实现步骤： 1、从T[0]开始比较； 2、若与给定的元素x相同，则查找结束；反之，则与序列T的下一个元素进行比较； 3、重复步骤二，直至找到与给定关键字x相同的元素，返回该元素的下标；若序列T中的元素全部完成与x的比较后，仍未找到与x相同的值，则返回0。

顺序查找算法查找给定元素的过程（假设x=6）： 1、初始化数组T 2、与T[0]比较，T[0]=1<6，继续往后比较 3、与T[1]比较，T[1]=2<6，继续往后比较 4、与T[2]比较，T[2]=3<6，继续往后比较 5、与T[3]比较，T[3]=4<6，继续往后比较 6、与T[4]比较，T[4]=5<6，继续往后比较 7、与T[5]比较，T[5]=6==6，找到给定元素x，结束查找，返回下标5

二分查找算法原理：假设序列T中元素是按升序排列，将T中间位置记录的关键字T[mid]与查找关键字x比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字T[mid]大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

二分查找算法实现步骤： 1、定义左边界left与右边界right，中间下标mid，其中，left = 0，right = n - 1，mid = (left + right) / 2； 2、从T[mid]开始比较，若T[mid] == x，则查找结束，返回下标mid；若T[mid] > x，则right = mid - 1；若T[mid] < x，则left = mid + 1； 3、若left > right，则表明给定元素x不在序列T中，查找失败，返回0。

二分查找算法查找给定元素的过程（假设x=6）： 1、初始化数组T，left = 0，right = 8，mid =（0 + 8）/ 2 = 4 2、与T[4]比较，T[4]=5<6，left = mid + 1 = 5，mid =（5 + 8）/ 2 = 6 3、与T[6]比较，T[6]=7>6，right = mid - 1 = 5，mid =（5 + 5）/ 2 = 5 4、与T[5]比较，T[5]=6==6，找到给定元素x，结束查找返回下标5。

3.设计

n表示序列T中的元素个数顺序查找算法查找给定元素的伪代码：

int Order_search(int T[], int n, int x) {
          
   
int i;
	for (i = 0; i < n; i++){
          
   
		if (T[i] == x) {
          
   
			返回下标
		}
	}
	return 0;
}

二分查找算法查找给定元素的伪代码：

int Binary_search(int T[], int n, int x) {
          
   
	int left, right, mid;
	初始化左边界，右边界
	while (left <= right){
          
   
		更新中间下标mid
		if (T[mid] == x) {
          
   
			返回下标
		}
		else{
          
   
			if (T[mid] > x) {
          
   
				更新右边界right
			}
			else{
          
   
				更新左边界left
			}
		}
	}
	return 0;
}