数据结构--基础算法|基础算法之五-查找( 折半查找)

折半查找 又称为二分查找。这种查找方法要求查找表的数据是线性结构保存,并且还要求查找表中的数据是按关键字由小到大有序排列。
折半查找(二分查找)是一种简单而又高效的查找算法,其查找长度至多为㏒2n+1(判定树的深度),平均查找长度为㏒2(n+1)-1,效率比顺序查找要高,但折半查找只能适用于顺序存储有序表(如对线性链表就无法有效地进行折半查找)。

经典非递归算法:

// 非递归折半 int binary_search(int search_table[],int length,int key) { // 最低位置索引low、最高位置索引high、中间位置索引mid // 中间位置的可能情况 // length为奇数时,mid 为正中间位置 mid的左侧和右侧用于同样数目的元素 // length为偶数时,mid为正中间往左的那一个元素正中间为小数,正中间往左的那一个位置才是(Low+High)/2 // low与high的关系 // 正常情况下lowhigh 未找到与key相同的元素 int low=0; int high=length-1; int mid=(low+high)/2; while(low<=high){mid=(low+high)/2; //找到与key相等的一个元素位置 if(search_table[mid]==key) return mid; if (search_table[mid]>key) high=mid-1; else low=mid+1; } return -1; }



经典递归算法:

//递归折半 int binary_search(int search_table[],int low,int high,int key) { if (low>high) return -1; int mid=(low+high)/2; if (search_table[mid]==key) return mid; if (search_table[mid]



返回重复值得最低位置索引:

// 非递归折半 // 找最低位置 int binary_search_Low(int search_table[],int length,int key) { // 最低位置索引、最高位置索引、中间位置索引 // 中间位置的可能情况 // length为奇数时,mid 为正中间位置 mid的左侧和右侧用于同样数目的元素 // length为偶数时,mid为正中间往左的那一个元素正中间为小数,正中间往左的那一个位置才是(Low+High)/2 // low与high的关系 // 正常情况下lowhigh 未找到与key相同的元素 int low=0; int high=length-1; int mid=(low+high)/2; while(low<=high){mid=(low+high)/2; //找到与key相等的一个元素位置 if(search_table[mid]==key) {//找最低位置 while(mid>0){if (search_table[mid-1]==key) mid=mid-1; else break; } return mid; }if (search_table[mid]>key) high=mid-1; else low=mid+1; } return -1; }

【数据结构--基础算法|基础算法之五-查找( 折半查找)】

返回重复值得最高位置索引:

// 非递归折半 // 找最高位置 int CComputerNumDlg::binary_search_High(int search_table[],int length,int key) { // 最低位置索引、最高位置索引、中间位置索引 // 中间位置的可能情况 // length为奇数时,mid 为正中间位置 mid的左侧和右侧用于同样数目的元素 // length为偶数时,mid为正中间往左的那一个元素正中间为小数,正中间往左的那一个位置才是(Low+High)/2 // low与high的关系 // 正常情况下lowhigh 未找到与key相同的元素 int low=0; int high=length-1; int mid=(low+high)/2; while(low<=high){mid=(low+high)/2; //找到与key相等的一个元素位置 if(search_table[mid]==key) {//找最高位置 while(midkey) high=mid-1; else low=mid+1; } return -1; }



    推荐阅读