二分查找

# Leetcode T704 二分查找

# 关于

第一篇刷题水文当然要从最简单的数组开始啦～

# 题目描述

一个 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.com/problems/binary-search

# 分析

这是一个数组的题，考察的知识点是二分查找，这不是废话吗？题目明摆写着呢。

还是好好分析一下，这类题目如果直接暴力遍历的话，时间复杂度为 O (n)，数组元素比较多的情况下，应该会超时吧

这时要关注一下题目给的条件：

• 有序的（升序）整型数组
• 可以假设 nums 中的所有元素是不重复的

这两个条件就是为二分查找量身打造的，对于二分查找，一定要满足元素有序的条件，不然得到的结果肯定是错的，那这题当然是用二分查找啦

# 思路

先定义两个整型变量 left，right 和 mid，约定要查找的目标 index 的索引位置在区间 [left, right] 内（注意，这里是闭区间，如果是左闭右开的话，对应的算法有所不同）。对于每一对 left 和 right 值，始终让 mid = (left + right) / 2，比较 nums [mid] 和 target 的大小：

• target <nums [mid]：说明 target 的索引位置在 [left, mid)，此时更新 right 为 mid - 1
• target = nums [mid]：此时的 mid 就是所求值
• target > nums [mid]：说明 target 的索引位置在 (mid, right]，此时更新 left 为 mid + 1

# 复杂度分析

• 时间复杂度：O (logn)，其中 n 是数组的长度
• 空间复杂度：O (1)

# 代码（Java 语言描述）

package T704;
/**
 * 简单地不能再简单的二分查找
 * */
class Solution {
    public int search(int[] nums, int target) {
        //这里假设nums[target]的索引在区间[left, right]内，注意这里是闭区间
        int left = 0;
        int right = nums.length;
        int mid;
        while(left <= right){
            mid = (left + right) / 2;
            //找到
            if(nums[mid] == target){
                return mid;
            }else if(target < nums[mid]){
                //说明target在左边
                right = mid - 1;
            }else{
                //说明target在右边
                left = mid + 1;
            }
        }
        //没找到，返回-1
        return -1;
    }
}

# 算法对比

这么简单的二分查找肯定是标准答案啦（等到别的题我就知道错了）