leetcode 704. 二分查找

leetcode 704. 二分查找

题目描述

704. 二分查找

给定一个 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]之间。

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/binary-search 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

法1

方法1:二分法
题目已经描述得很清楚了,使用二分法查找数,二分法也非常适用于这种排序的数组,对时间有很多优化

具体实现方法如下:

我们使用二分查找算法来搜索目标值。

1. 首先，我们将数组的左边界 left 设置为 0，右边界 right 设置为数组长度减 1。
2. 然后，我们在每一步迭代中计算中间元素的下标 mid。如果 nums[mid] 等于目标值 target，则返回 mid。如果 nums[mid] 小于目标值 target，则更新 left 为 mid + 1，表示目标值可能在右半部分。如果 nums[mid] 大于目标值 target，则更新 right 为 mid - 1，表示目标值可能在左半部分。当 left 大于 right 时，表示目标值不存在于数组中，因此返回 -1。

• 时间复杂度(O(logn))
• 空间复杂度(O(1))

执行结果

法1

func search(nums []int, target int) int {
 left, right := 0, len(nums)-1

 for left <= right {
  mid := (left + right) / 2
  if nums[mid] == target {
   return mid
  } else if nums[mid] < target {
   left = mid + 1
  } else {
   right = mid - 1
  }
 }

 return -1
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 20 ms , 在所有 Go 提交中击败了 99.64% 的用户 内存消耗： 6.5 MB , 在所有 Go 提交中击败了 69.89% 的用户 通过测试用例： 47 / 47 炫耀一下:

法2

法3