高端网站制作系统,高端品牌女装连衣裙,怎么用手机自己做网站,wordpress增加小工具二分法#xff1a;顾名思义#xff0c;把问题一分为2的处理#xff0c;是一种常见的搜索算法#xff0c;用于在有序数组或这有序列表中查找指定元素的位置#xff0c;它的思想是将待搜索的区间不断二分#xff0c;然后比较目标值与中间元素的大小关系#xff0c;然后确定… 二分法顾名思义把问题一分为2的处理是一种常见的搜索算法用于在有序数组或这有序列表中查找指定元素的位置它的思想是将待搜索的区间不断二分然后比较目标值与中间元素的大小关系然后确定下一步的搜索的方向 以下是二分法的基本步骤确定搜索区间的起始位置 left 和结束位置 right通常初始时 left 为数组的第一个元素的索引right 为数组的最后一个元素的索引。在每一次循环中计算中间位置 mid即 mid (left right) / 2。比较目标值与中间元素的大小关系如果目标值等于中间元素则找到了目标值返回中间元素的索引。如果目标值小于中间元素则目标值可能在左半部分更新 right mid - 1。如果目标值大于中间元素则目标值可能在右半部分更新 left mid 1。重复步骤 2-3直到找到目标值或搜索区间为空即 left right。 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 思路 标签二分查找 过程 设定左右指针 找出中间位置并判断该位置值是否等于 target nums[mid] target 则返回该位置下标 nums[mid] target 则右侧指针移到中间 nums[mid] target 则左侧指针移到中间 时间复杂度O(logN) c代码实现
class Solution {
public:int search(vectorint nums, int target) {int left0;int rightnums.size()-1;while(leftright){int midleft(right-left)/2;if(nums[mid]target){return mid;}else if(nums[mid]target){leftmid1;}elserightmid-1;}return -1;}
}; c语言写法 int search(int* nums, int numsSize, int target) {int left0;int rightnumsSize-1;while(leftright){int midleft(right-left)/2;if(nums[mid]target){leftmid1;}else if(nums[mid]target){rightmid-1;}elsereturn mid;}return -1;
} 用递归来做
int binarySearchRecursive(int* nums, int left, int right, int target) {if (left right) {return -1; // 搜索区间为空未找到目标值}int mid left (right - left) / 2;if (nums[mid] target) {return mid; // 找到目标值返回索引} else if (nums[mid] target) {return binarySearchRecursive(nums, mid 1, right, target); // 目标值可能在右半部分} else {return binarySearchRecursive(nums, left, mid - 1, target); // 目标值可能在左半部分}
}
