首页 > 代码库 > 二分查找
二分查找
一、普通的二分查找算法:
1 int BS(int a[], int k, int n) 2 { 3 int low = 0; 4 int high = n - 1; 5 while (low <= high) 6 { 7 int mid = (high - low) / 2 + low; 8 if (a[mid] == k) 9 return mid; 10 else 11 if (a[mid] < k) 12 low = mid + 1; 13 else 14 high = mid - 1; 15 } 16 return -1; 17 } 18 int main() 19 { 20 int a[] = { 1,1, 3, 6, 8, 9, 9, 10 }; 21 cout << BS(a, 0, 8) << endl; 22 system("pause"); 23 return 0; 24 }
二、查找关键元素在有序数组中的首次出现位置:
1 int lowerBoner(int a[], int k,int n) 2 { 3 int low = 0; 4 int high = n - 1; 5 while (low < high) 6 { 7 int mid = (high - low) / 2 + low; 8 if (a[mid] < k) 9 low = mid+1; 10 else 11 high = mid; 12 } 13 if (low >= n || a[low] != k) 14 return -1; 15 else 16 return low; 17 } 18 int main() 19 { 20 int a[] = { 1,1, 3, 6, 8, 9, 9, 10 }; 21 cout << lowerBoner(a, 9, 7) << endl; 22 system("pause"); 23 return 0; 24 }
三、查找关键元素在有序数组中的末次出现位置:
1 int upperbound(int a[], int k,int n){ 2 int low = 0; 3 int high = n - 1; 4 while (low < high){ 5 int mid = low + (high - low + 1) / 2; 6 if (a[mid] > k){ 7 high = mid - 1; 8 } 9 else{ 10 low = mid; 11 } 12 } 13 if (low >= n || a[low] != k){ 14 return -1; 15 } 16 else{ 17 return low; 18 } 19 } 20 21 int main() 22 { 23 int a[] = { 1,1, 3, 6, 8, 9, 9, 10 }; 24 cout << upperbound(a, 1, 8) << endl; 25 system("pause"); 26 return 0; 27 }
二分查找
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。