个人或主题网站建设 实验体会,网站开发可退税,lnmp wordpress ssl,软件是怎么做的文章目录1.数据有序且无重复#xff0c;查找给定值2.数据有序且有重复#xff0c;查找第1个给定的值3.查找最后一个值等于给定值的元素4.查找第一个大于等于给定值的元素5.查找最后一个小于等于给定值的元素6.查找IP归属#xff08;利用上面#5代码#xff09;7.循环有序数组…
文章目录1.数据有序且无重复查找给定值2.数据有序且有重复查找第1个给定的值3.查找最后一个值等于给定值的元素4.查找第一个大于等于给定值的元素5.查找最后一个小于等于给定值的元素6.查找IP归属利用上面#5代码7.循环有序数组查找给定值1.数据有序且无重复查找给定值
/*** description: 数据有序(小到大)且无重复查找给定值* author: michael ming* date: 2019/4/16 18:54* modified by: */
#include iostream
#define N 10
using namespace std;
int binarySearch_simple(int *arr,size_t n,int num)
{size_t low 0, high n-1;while(low high){size_t mid low(high-low)/2;if(arr[mid]num)return mid;else if(arr[mid] num)low mid1;elsehigh mid-1;}return -1;
}
int main()
{cout 数组打印如下 endl;int arr[N] {1,2,3,4,5,6,7,8,9,10};for(int i 0; i N; i)cout arr[i] ;cout 请输入要查找的数将返回下标不存在返回-1;int num;cin num;cout num 的下标是 binarySearch_simple(arr,N,num) endl;
}2.数据有序且有重复查找第1个给定的值
/*** description: 查找第一个等于给定值的元素* author: michael ming* date: 2019/4/16 19:19* modified by: */
#include iostream
#define N 10
using namespace std;
int binarySearch_simple(int *arr,size_t n,int num)
{size_t low 0, high n-1;while(low high){size_t mid low(high-low)/2;if(arr[mid]num){if(mid 0 || arr[mid-1] ! num) //第一个元素或者前一个元素不等于numreturn mid;else //否则要查找的元素在前面high mid-1;}else if(arr[mid] num)low mid1;elsehigh mid-1;}return -1;
}
int main()
{cout 数组打印如下 endl;int arr[N] {1,1,2,2,4,5,6,7,8,9};for(int i 0; i N; i)cout arr[i] ;cout 请输入1个数将返回查找第一个等于给定值的元素的下标不存在返回-1;int num;cin num;cout num 的下标是 binarySearch_simple(arr,N,num) endl;
}3.查找最后一个值等于给定值的元素
/*** description: 查找最后一个值等于给定值的元素* author: michael ming* date: 2019/4/16 20:24* modified by: */
#include iostream
#define N 10
using namespace std;
int binarySearch_simple(int *arr,size_t n,int num)
{size_t low 0, high n-1;while(low high){size_t mid low(high-low)/2;if(arr[mid]num){if(mid n-1 || arr[mid1] ! num) //最后一个元素了或者后面的不等于numreturn mid;else //否则最后一个元素还在后面low mid1;}else if(arr[mid] num)low mid1;elsehigh mid-1;}return -1;
}
int main()
{cout 数组打印如下 endl;int arr[N] {1,1,2,2,4,5,6,8,8,9};for(int i 0; i N; i)cout arr[i] ;cout 请输入要查找的数将返回最后一个符合的下标不存在返回-1;int num;cin num;cout num 的下标是 binarySearch_simple(arr,N,num) endl;
}4.查找第一个大于等于给定值的元素
/*** description: 查找第一个大于等于给定值的元素* author: michael ming* date: 2019/4/16 20:54* modified by: */
#include iostream
#define N 10
using namespace std;
int binarySearch_simple(int *arr,size_t n,int num)
{size_t low 0, high n-1;while(low high){size_t mid low(high-low)/2;if(arr[mid] num) //当找到要求的值时{if(mid 0 || arr[mid-1] num) //判断是第一个元素或者前面的比我小return mid; //当前满足else //否则满足要求的还在前面high mid-1;}else if(arr[mid] num)low mid1;}return -1;
}
int main()
{cout 数组打印如下 endl;int arr[N] {1,2,2,4,5,6,7,8,9,10};for(int i 0; i N; i)cout arr[i] ;cout 请输入一个数将返回第一个大于等于它的下标不存在返回-1;int num;cin num;cout num 的下标是 binarySearch_simple(arr,N,num) endl;
}5.查找最后一个小于等于给定值的元素
/*** description: 查找最后一个小于等于给定值的元素* author: michael ming* date: 2019/4/16 23:09* modified by: */
#include iostream
#define N 10
using namespace std;
int binarySearch_simple(int *arr,size_t n,int num)
{size_t low 0, high n-1;while(low high){size_t mid low(high-low)/2;if(arr[mid] num)high mid-1;else if(arr[mid] num){if(mid n-1 || arr[mid1] num) //最后一个元素或者后面的比它大了return mid; //它是最后一个小于等于的elselow mid1; //否则后面还有满足的下限往上加}}return -1;
}
int main()
{cout 数组打印如下 endl;int arr[N] {1,2,2,4,5,6,7,10,10,10};for(int i 0; i N; i)cout arr[i] ;cout 请输入一个数返回最后一个小于等于给定值的元素的下标不存在返回-1;int num;cin num;cout num 的下标是 binarySearch_simple(arr,N,num) endl;
}6.查找IP归属利用上面#5代码
/*** description: 查找ip地址归属找到最后一个区间开始地址ip的* author: michael ming* date: 2019/4/16 23:38* modified by: */
#include iostream
#include binarySearch_findLastLessNum.cpp
int main()
{int start[5] {101,201,301,401,501}; //假设为ip起始地址A,B,C,D,Eint end[5] {200,300,400,500,600}; //对应ip终止地址size_t ip;while(1){std::cout 请输入要查询的ip: ;std::cin ip;int index binarySearch_simple(start,5,ip); //在ip区间头里查找最后一个我的if(index ! -1 ip end[index])switch(index){case 0:std::cout ip in city A std::endl;break;case 1:std::cout ip in city B std::endl;break;case 2:std::cout ip in city C std::endl;break;case 3:std::cout ip in city D std::endl;break;case 4:std::cout ip in city E std::endl;break;}elsestd::cout ip not found! std::endl;}
}7.循环有序数组查找给定值
例如4,5,6,7,1,2,3 循环数组性质以数组中间点为分区数组分成一个有序数组和一个循环有序数组。
如果首元素 arr[low] arr[mid]左半部分有序右半部分循环有序 如果首元素 arr[low] arr[mid]右半部分有序左半部分循环有序 判断查找的数是否在有序的半边范围内更新上下限 时间复杂度为 O(logN)。
/*** description: 循环有序数组查找给定值* author: michael ming* date: 2019/4/17 0:25* modified by: */
#include iostream
#define N 10
int circular_Arr_BS(int *arr, size_t n, int num)
{size_t low 0, high n-1;while(low high){size_t mid low(high-low)/2;if(arr[mid] num)return mid;if(arr[mid] arr[low]) //转折点在左边,右边有序{if(arr[mid] num num arr[high]) //数据在右边low mid1;elsehigh mid-1;}else //转折点在右边左边有序{if(arr[low] num num arr[mid]) //数据在左边high mid-1;elselow mid1;}}return -1;
}
int main()
{int arr[N] {4,5,6,7,8,9,10,1,2,3};size_t mid (N-1)/2;int num;std::cin num;std::cout circular_Arr_BS(arr,N,num);return 0;
}
