网站建设存在的具体问题,论坛网站方案,网络营销的基础与前提是什么理论,枣庄手机网站建设报价前言 在之前的博客中#xff0c;我给大家介绍了最基础的二分查找法#xff08;没学的话点我点我#xff01;#xff09;
今天我将带大家学习二分法的六种变形如何使用#xff0c;小伙伴们#xff0c;快来开始今天的学习吧#xff01; 文章目录 1#xff0c;查找第一个…前言 在之前的博客中我给大家介绍了最基础的二分查找法没学的话点我点我
今天我将带大家学习二分法的六种变形如何使用小伙伴们快来开始今天的学习吧 文章目录 1查找第一个从左到右 目标值的若不存在返回 -12查找第一个 目标值的3查找第一个 目标值的4查找最后一个 目标值的 若不存在返回- 15查找最后一个 目标值的6查找最后一个 目标值的总结 1查找第一个从左到右 目标值的若不存在返回 -1
与原版二分法其实差不多当一个数组中有重复的目标值时使用该方法可以找到从左到右第一个等于目标值的下标。 因为我们要找的是第一个等于目标值的下标那我们不仅仅在arr[mid] key时去左边找在arr[mid] key我们也要去找因为我们需要要最左边等于目标值的下标。 注意事项 最后我们要判断left是否越界(left 有可能等于数组元素的个数)而且最后arr[left]是否等于要找的key。 代码
int efcz(int* arr, int key,int left,int right)
{int len right1;//数组长度元素个数int mid (left right) / 2;while (left right){mid (left right) / 2;if (arr[mid] key){right mid - 1;}if (arr[mid] key){left mid 1;}}if (left lenarr[left] ! key)//判断一下是否找到元素return -1;elsereturn left;
}
int main()
{int arr[10] { 1,2,3,5,5,5,5,5,5,6 };//创建数组int key 5;//目标值为5int left 0;//设置左右起点int right sizeof(arr) / sizeof(arr[0]);printf(%d, efcz(arr, key,left,right));//进入二分查找函数return 0;
}2查找第一个 目标值的
这次我们需要查找第一个大于等于目标值的下标这次我们不需要判断left越界如果越界就说明没有找到说明整个数组都比目标值要小。 代码
//思路和第一种一样我就不加注释了如果不懂可以私信问我
int efcz(int* arr, int key, int left, int right)
{int mid (left right) / 2;while (left right){mid (left right) / 2;if (arr[mid] key){right mid - 1;}if (arr[mid] key){left mid 1;}}return left;
}
int main()
{int arr[10] { 1,2,3,5,5,5,5,5,6,8 };int key 7;int left 0;int right sizeof(arr) / sizeof(arr[0]);printf(%d, efcz(arr, key, left, right));return 0;
}3查找第一个 目标值的
这次我们需要查找第一个大于目标值的下标这次我们同样不需要判断left越界如果越界就说明没有找到说明整个数组都比目标值要小。 另外我们需要改变一下函数内部的判断条件当arr[mid] key时left mid 1 因为我们不是要找相等的是要找大于目标值的。 代码
//思路和第一种一样我就不加注释了如果不懂可以私信问我
int efcz(int* arr, int key, int left, int right)
{int mid (left right) / 2;while (left right){mid (left right) / 2;if (arr[mid] key){right mid - 1;}if (arr[mid] key){left mid 1;}}return left;
}
int main()
{int arr[10] { 1,2,3,5,5,5,5,5,6,8 };int key 5;int left 0;int right sizeof(arr) / sizeof(arr[0]);printf(%d, efcz(arr, key, left, right));return 0;
}4查找最后一个 目标值的 若不存在返回- 1
因为我们要找的是第一个等于目标值的下标那我们不仅仅在arr[mid] key时去右边找在arr[mid] key我们也要去找因为我们需要要最右边边等于目标值的下标。 注意事项 最后我们要判断right是否越界(right 有可能等于-1)而且最后arr[right]是否等于要找的key。 代码
//思路和第一种一样我就不加注释了如果不懂可以私信问我
int efcz(int* arr, int key, int left, int right)
{int mid (left right) / 2;while (left right){mid (left right) / 2;if (arr[mid] key){right mid - 1;}if (arr[mid] key){left mid 1;}}if (right 0 arr[right] key)//判断是否找到return right;elsereturn -1;
}
int main()
{int arr[10] { 1,2,3,5,5,5,5,5,6,8 };int key 5;int left 0;int right sizeof(arr) / sizeof(arr[0]);printf(%d, efcz(arr, key, left, right));return 0;
}5查找最后一个 目标值的
这次我们需要查找第一个小于等于目标值的下标这次我们不需要判断right越界如果越界就说明没有找到说明整个数组都比目标值要大。 代码
//思路和第一种一样我就不加注释了如果不懂可以私信问我
int efcz(int* arr, int key, int left, int right)
{int mid (left right) / 2;while (left right){mid (left right) / 2;if (arr[mid] key){right mid - 1;}if (arr[mid] key){left mid 1;}}return right;
}
int main()
{int arr[10] { 1,2,3,5,5,5,5,5,6,8 };int key 4;int left 0;int right sizeof(arr) / sizeof(arr[0]);printf(%d, efcz(arr, key, left, right));return 0;
}6查找最后一个 目标值的
这次我们需要查找第一个小于目标值的下标这次我们同样不需要判断right越界如果越界就说明没有找到说明整个数组都比目标值要大。 另外我们也需要改变一下函数内部的判断条件当arr[mid] key时right mid - 1因为我们不是要找相等的是要找小于目标值的。 代码
//思路和第一种一样我就不加注释了如果不懂可以私信问我
int efcz(int* arr, int key, int left, int right)
{int mid (left right) / 2;while (left right){mid (left right) / 2;if (arr[mid] key){right mid - 1;}if (arr[mid] key){left mid 1;}}return right;
}
int main()
{int arr[10] { 1,2,3,5,5,5,5,5,6,8 };int key 5;int left 0;int right sizeof(arr) / sizeof(arr[0]);printf(%d, efcz(arr, key, left, right));return 0;
}总结
我认为可以分两组记忆这六种变形前三组一类后三组一类前三组都是返回left后三组都是返回right同时我们会发现第一种和第四种第二种和第五种第三种和第六种都十分的相似所以自己练练就能掌握而且不容易忘记本期的分享就到这里如果觉得博主讲的不错的话千万不要忘记给博主一个关注点赞收藏哦~小伙伴们我们下期再见
