今天刷的LeetCode编程题目是704. 二分查找,以下是学习笔记:
二分查找算法详解:
在升序数组nums 中寻找目标值target,对于特定下标i,比较nums[i] 和 target 的大小:
1、如果nums[i]=target,则下标i即为要寻找的下标;
2、如果nums[i]>target,则target 只可能在下标i的左侧;
3、如果 nums[i]<target,则target 只可能在下标i的右侧。
适用场景:在有序且不重复数组中查找目标值。
算例:
题目条件:
1、在一个有序(升序)数组nums中找出目标值target,并返回下标。
2、可以假设数组中所有元素不重复。
条件1保证了如果这个数组中存在目标值target,那么一定可以查找到目标值target并返回下标。假设这个数组是乱序的并且目标值target存在于前半部分(当然也可以假设目标值target在数组的后半部分),那么用二分法查找时有可能找不到,下面的例子可以说明这个问题:
条件2保证了查找结果返回唯一的下标。如果数组nums中存在目标值target,且有多个,那么程序将进入死循环。
例如:
void search(vector<int>& nums, int target) {int low = 0, high = nums.size() - 1, mid = 0;while (low <= high){mid = low + (high - low) / 2;if (nums[mid] == target){cout<< mid<<endl;}else if (nums[mid]<target){low = mid + 1;}else{high = mid - 1;}}cout<< -1<<endl;}int main(){vector<int> nums = {-1,0,3,5,9,9,12};search(nums, 9);//system("PAUSE");return 0;}
以上代码在VS Professional 上的运行结果为无限打印数字5:
所以根据题目条件和二分查找算法的适用场景,LeetCode704. 二分查找C++题解代码如下:
class Solution {public:int search(vector<int>& nums, int target) {int low=0,high=nums.size()-1,mid=0;while(low<=high){mid=low+(high-low)/2;if(nums[mid]==target){return mid;}else if(nums[mid]<target){low=mid+1;}else {high=mid-1;}}return -1;}};
参考文章:
https://leetcode-/problems/binary-search/solution/er-fen-cha-zhao-by-leetcode-solution-f0xw/
https://leetcode-/problems/binary-search/solution/er-fen-cha-zhao-xiang-jie-by-labuladong/
https://leetcode-/problems/binary-search/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-er-fe-ajox/
如果觉得《单片机攻城之LeetCode刷题-704. 二分查找》对你有帮助,请点赞、收藏,并留下你的观点哦!