折半查找举例已知如下11个元素的有序表: (0513192137566475808892),请查找关键字为21 的数据元素的查找思路。 Low指向待查元mid指向待查元素所在]h指向待查元素所 素所在区间的下 区间的中间位置 在区间的上界 界 解:①先设定3个辅助标志: low, high, mid 显然有:md=L(ow+high)/2」 ②运算步骤: (1)low=0,high=10,故mid=5,待查范围是[0,10]; (2)若S.list[mid].key<key,说明key∈[mid+1,high] 则令:1oW=md+1;重算md=L(ow+high)/2; (3)若S.list[mid].key>key,说明key∈[low,mid-1 则令:high=mid-1;重算md; (4)若S.list[md].key==key,说明查找成功,元素序号=mid; 结束条件:(1)查找成功:S.list[mid].key=key (2)查找不成功:high≤low(意即区间长度小于0)
11 ② 运算步骤： (1) low =0,high =10 ,故mid =5 ，待查范围是 [0,10]； (2) 若 S.list[mid].key < key，说明 key[ mid+1,high] ， 则令：low =mid+1;重算 mid＝ (low+high)/2；. (3) 若 S.list[mid].key > key，说明key[low ,mid-1]， 则令：high =mid–1;重算 mid ； (4)若 S.list[ mid ].key= = key，说明查找成功，元素序号=mid; 结束条件：（1）查找成功 ： S.list[mid].key = key （2）查找不成功 ： high≤low （意即区间长度小于0） 解：① 先设定3个辅助标志:low,high,mid， 折半查找举例： Low指向待查元 素所在区间的下 界 high指向待查元素所 在区间的上界 mid指向待查元素所在 区间的中间位置 已知如下11个元素的有序表： （05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为21 的数据元素的查找思路。 显然有：mid= (low+high)/2
(2)算法的实现 int Binary Search(SeqList S, DataType x) int low=0,high=S.size-1;/确定初始査找区间上下界 int mid. while(low <= high) mid=(1oW+high)/2;//确定初始查找区间中心位置 if(S.1ist[mid].key==x.key) return mid;/查找成功 else if(S. list[mid]. key x key) low= mid +1 else if(S.list[mid]. key >x key) high =mid return -1 //查找失败
12 (2)算法的实现 int BinarySearch(SeqList S, DataType x) {int low = 0, high = S.size-1;/确定初始查找区间上下界 int mid; while(low <= high) { mid=(low + high)/2;//确定初始查找区间中心位置 if(S.list[mid].key == x.key) return mid;//查找成功 else if(S.list[mid].key < x.key) low = mid + 1; else if(S.list[mid].key > x.key) high = mid - 1; } return -1; //查找失败 }