Leetcode 704 Binary Search

题目思路代码

题目

Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.

Example 1: Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4

Example 2: Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1

Note: You may assume that all elements in nums are unique. n will be in the range [1, 10000]. The value of each element in nums will be in the range [-9999, 9999].

思路

binary search虽然是比较基础的算法，但是写起来还是有很多细节的地方需要去注意。下面的区间index范围都是包含左不包含右。

进入递归的时候记得扣掉mid这个数，否则到只有一个数但是结果应该是-1的时候，一直会被分割成0个和1个数，程序不会结束。总长度为奇数个时注意检查是否是左右对半分的，为偶数的时候稍微复杂些，考虑两个数$[A,B]$的情况，mid取A或B的index都可以，假设取A，要确保递归进入的左侧是lo到mid（左闭右开不包含mid），右侧是mid+1到hi考虑停止条件，2中从两个元素进入到0个元素时，有lo=hi（mid为A的index是下一步的hi），再考虑从1个元素到0个元素时，左侧区间为lo到mid，右侧区间为mid+1到hi，两侧都为0个元素，此时都有lo=hi，可知停止条件为lo == hi。

代码

class Solution { public int search(int[] nums, int target) { return binarySearch(nums, target, 0, nums.length); } public int binarySearch(int[] nums, int target, int lo, int hi) { if (lo >= hi) return -1; int mid = (lo + hi) / 2; if (nums[mid] == target) return mid; if (nums[mid] < target) return binarySearch(nums, target, mid + 1, hi); return binarySearch(nums, target, lo, mid); } }