LeetCode题解：704.二分查找

ゝ一世哀愁。 2022-12-27 07:30 147阅读 0赞

# 二分查找（easy） #

> 更好的阅读体验应该是：
> 
> 1.  审题-思考
> 2.  答题
> 3.  整理-归纳

## 一、题目 ##

[LeetCode：704.二分查找][LeetCode_704.]

给定一个 `n` 个元素有序的（升序）整型数组 `nums` 和一个目标值 `target` ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

**示例:**

输入: nums = [-1,0,3,5,9,12], target = 9
    输出: 4
    解释: 9 出现在 nums 中并且下标为 4

你可以假设 nums 中的所有元素是不重复的。

## 二、二分法解题 ##

二分查找是一种基于比较目标值和数组中间元素的教科书式算法。

*  如果目标值等于中间元素，则找到目标值。
 *  如果目标值较小，继续在左侧搜索。
 *  如果目标值较大，则继续在右侧搜索。

时间复杂度：`O(logN)`。  
空间复杂度：`O(1)`。

**模版 I**

1.  确定初始的左右边界:
    
     *  `left`: 0
     *  `right`: nums.length-1
     *  `mid`: (left + right) >> 1
2.  如果中间元素值`nums[mid]` < target：证明中间值左侧包括中间值都不符合要求，可以直接排除，`left = mid + 1`
3.  如果中间元素值`nums[mid]`：证明中间值右侧包括中间值都不符合要求，可以直接排除，`right = mid - 1`
4.  如果中间元素值`nums[mid]` = target：直接返回`mid`的下标
5.  重新定义了左右边界，也需要重新计算中间值，我们需要继续进行范围的排除
6.  定义搜索的条件，应该是搜索区间都不为空，即`left <= right`

**Javasciprt 代码**

## 三、写在最后 ##

上面的代码就是二分法模板 I，看过我的二分法总结的同学应该知道，凭借这套模版以及对应的分析，类似的问题应该难不住你了。

如果对你有所帮助不妨给本项目的[github 点个 star][github _ star]，这是对我最大的鼓励。

**关于我**

*  花名：余光
 *  WX：j565017805
 *  沉迷 JS，水平有限，虚心学习中

**其他沉淀**

*  [Github：JavaScript 版 LeetCode 题解][Github_JavaScript _ LeetCode]
 *  [在线版：前端进阶笔记][Link 1]
 *  [CSDN博客汇总][CSDN]

![20200602155947301.png][]

[LeetCode_704.]: https://leetcode-cn.com/problems/binary-search/
[github _ star]: https://github.com/webbj97/summary
[Github_JavaScript _ LeetCode]: https://webbj97.github.io/leetCode-Js/
[Link 1]: https://webbj97.github.io/summary/
[CSDN]: https://yuguang.blog.csdn.net/
[20200602155947301.png]: /images/20221120/fce74227d71247a586bbe630d6bdd726.png