您的问题似乎不完整,您是想询问关于C语言编程的某个具体问题吗?比如C语言的语法、编程技巧、项目开发等。请提供更具体的信息,这样我才能给出更准确的回答。
摘要:二分搜索法 ##定义 二分法查找,也称为折半法,是一种在有序数组中查找特定元素的搜索算法。 适用范围 当数据量很大并且有序时,适宜采用该方法。 基本思想 假设数据是按升序排序的,对于给定值key,从序列的中间位置k开始比较, 如果当前位置a
二分搜索法
定义
二分法查找,也称为折半法,是一种在有序数组中查找特定元素的搜索算法。
适用范围
当数据量很大并且有序时,适宜采用该方法。
基本思想
假设数据是按升序排序的,对于给定值key,从序列的中间位置k开始比较,
如果当前位置arr[k] 值等于key,则查找成功;
若key小于当前位置值arr[k],则在数列的前半段中查找,arr[low, mid - 1];
若key大于当前位置值arr[k],则在数列的后半段中继续查找arr[mid + 1, high],
直到找到为止,时间复杂度:O(log(n))
算法难点
对边界条件细节掌握,也就是区间状态。区间状态基本为下边两种。
若是区间为[left, right]既while(left<=arr.Length-):更新状态方式left = mid + 1; right = mid - 1;
若是区间为[left, right)既while(left<arr.Length):更新状态方式left = mid + 1; right = mid;
代码实现(模板)
该代码是实现区间为[left,right]的。
public static int BinarySearch(int[] nums, int target)
{
// 避免当 target不存在与数组,多次进行循环运算
if (target < nums[0] || target > nums[nums.Length - 1])
{
return -1;
}
int left = 0, right = nums.Length - 1;
while (left <= right)
{
//1.此处避免数据量过大,超出int范围。2.位运算效率比较高
int mid = left + ((right - left) >> 1);
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid - 1;
}
return -1;
}
题目练习
给出的题目由易到难,熟练掌握二分法,及其边界处理问题。
704. 二分查找
//这道题是最简单的,也是我们二分法的模板。之后关于二分法的题目,都是基于此题给的变形。
