算法入门篇-二分查找（1）
一， 题目描述
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例1：
输入: nums = [1,2,3,5,9,10], target = 5输出: 3解释: 5 出现在 nums 中并且下标为 3
示例2：
输入: nums = [-5], target = 5输出: -1解释: 5 不存在 nums 中因此返回 -1
提示：
你可以假设 nums 中的所有元素是不重复的。n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间。
先不要往下滑，思考一分钟，你想如何解这道题
二， 解题思路
二分查找是一种基于比较目标值和数组中间元素的教科书式算法。
以下提供我初次看到此题的思路，
设置搜索范围，即开始，结尾索引
找到中间位置元素，
如果目标值等于中间元素，则找到目标值。
如果目标值较小，则将左侧设置为搜索范围。
如果目标值较大，则将右侧设置为搜索范围。
三，参考代码
LeetCode官方给出的代码：
class Solution {public int search(int[] nums, int target) {int pivot, left = 0, right = nums.length - 1;while (left <= right) {pivot = left + (right - left) / 2;if (nums[pivot] == target) return pivot;if (target < nums[pivot]) right = pivot - 1;else left = pivot + 1;}return -1;}}
我第一次写的代码：
class Solution {public int search(int[] nums, int target) {int begin = 0;int end = nums.length-1;while (true) {int center = begin + (end - begin) / 2;if (nums[center] == target) {return center;} else if (nums[center] > target) {end = center;} else {begin = center;}// 结束条件单独判断，退出循环if ((end - begin) <= 1) {if (nums[begin] == target) {return begin;} else if (nums[end] == target) {return end;} else {return -1;}}}}}
我的方法虽然比官方给出的代码要长，但占用内存更少，大家可以思考一下为啥。
四，复杂度分析
时间复杂度：O(logN)。
空间复杂度：
\mathcal{O}(1)
参考阅读LeetCode官方题解：
https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-by-leetcode/