❝
这是一道 「简单」 题
https://leetcode.cn/problems/binary-search❞
题目
给定一个 个元素，有序的（升序）整型数组 和一个目标值 ，写一个函数搜索 中的 ，如果目标值存在返回下标，否则返回 。
示例 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
提示：
-
你可以假设 中的所有元素是不重复的。 -
将在之间。 -
的每个元素都将在 之间。
题解
解题前我们先明确一下「二分查找的前提条件」：
-
目标函数（或者说待查找的序列）具有单调性，单调递增或递减。 -
具有边界。 -
可以通过索引进行访问。
毫无疑问，本题是完全符合上述条件的。
解题思路非常简单，就是拿目标值 和序列的中间值 进行比较：
-
如果 : 说明目标 的位置在 左边，在左半边继续找。 -
如果 : 说明目标 的位置在 右边，在右半边继续找。 -
如果 : 找到目标。
代码实现
Java
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = (left + right) / 2;
if(nums[mid] == target){
return mid;
}else if(nums[mid] < target){
left = mid + 1;
}else{
right = mid - 1;
}
}
return -1;
}
}
Go
func search(nums []int, target int) int {
left, right := 0, len(nums) - 1
for left <= right {
mid := (left + right) / 2
if target == nums[mid] {
return mid
}else if target < nums[mid] {
right = mid - 1
}else{
left = mid + 1
}
}
return -1
}
复杂度分析
时间复杂度： , N 为数组 的长度。
空间复杂度：。
– End –
如果觉得有所收获，就顺道点个关注吧！
原文始发于微信公众号（i余数）：【算法题解】66. 二分查找
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/193537.html
