折半查找
又称为二分查找。这种查找方法要求查找表的数据是线性结构保存,并且还要求查找表中的数据是按关键字由小到大有序排列。
折半查找(二分查找)是一种简单而又高效的查找算法,其查找长度至多为㏒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的关系 // 正常情况下low<high // low==high时,仅剩下最后一个需要判断的元素,此元素可能与key相同,也可能不同 // low>high 未找到与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]<key) return binary_search(search_table,low,mid-1,key); else return binary_search(search_table,mid+1,high,key); }
返回重复值得最低位置索引:
// 非递归折半 // 找最低位置 int binary_search_Low(int search_table[],int length,int key) { // 最低位置索引、最高位置索引、中间位置索引 // 中间位置的可能情况 // length为奇数时,mid 为正中间位置 mid的左侧和右侧用于同样数目的元素 // length为偶数时,mid为正中间往左的那一个元素 正中间为小数,正中间往左的那一个位置才是(Low+High)/2 // low与high的关系 // 正常情况下low<high // low==high时,仅剩下最后一个需要判断的元素,此元素可能与key相同,也可能不同 // low>high 未找到与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的关系 // 正常情况下low<high // low==high时,仅剩下最后一个需要判断的元素,此元素可能与key相同,也可能不同 // low>high 未找到与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<high-1){ 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; }