本文主要是介绍每日OJ题_算法_二分查找①_力扣704. 二分查找,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
二分查找算法原理
力扣704. 二分查找
解析代码
二分查找算法原理
二分查找一种效率较高的查找方法。但是,二分查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。一般步骤如下:
首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
以前学C/C++也写过二分查找的代码,直接刷题:
力扣704. 二分查找
704. 二分查找 - 力扣(LeetCode)
难度 简单
给定一个 n
个元素有序的(升序)整型数组 nums
和一个目标值 target
,写一个函数搜索 nums
中的 target
,如果目标值存在返回下标,否则返回 -1
。
示例 1:
输入:nums
= [-1,0,3,5,9,12],target
= 9 输出: 4 解释: 9 出现在nums
中并且下标为 4
示例 2:
输入:nums
= [-1,0,3,5,9,12],target
= 2 输出: -1 解释: 2 不存在nums
中因此返回 -1
提示:
- 你可以假设
nums
中的所有元素是不重复的。 n
将在[1, 10000]
之间。nums
的每个元素都将在[-9999, 9999]
之间。
class Solution {
public:int search(vector<int>& nums, int target) {}
};
解析代码
首先是有序的,就知道用二分了,简单题重拳出击:
class Solution {
public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while(left <= right){int mid = left + (right - left) / 2;if(nums[mid] > target){right = mid - 1;}else if(nums[mid] < target){left = mid + 1;}else{return mid;}}return -1;}
};
这篇关于每日OJ题_算法_二分查找①_力扣704. 二分查找的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!