[leetcode] 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].

分析：二分查找，要注意使用二分查找，数组必须是有序的。是一个必备的技能了。有递归版本和非递归版本。这里要注意无论是递归还是非递归，结束的条件都是low>high。代码如下：

非递归：

 1 class Solution {
 2     public int search(int[] nums, int target) {
 3         return helper(nums,target,0,nums.length-1);
 4     }
 5     private int helper(int[] nums, int target, int low, int high) {
 6         while ( low <= high ){
 7             int mid = ( low + high ) / 2;
 8             if ( nums[mid] == target ) return mid;
 9             if ( nums[mid] < target ) low = mid + 1;
10             if ( nums[mid] > target ) high = mid - 1;
11         }
12         return -1;
13     }
14 }

运行时间2ms。

递归版本：

 1 class Solution {
 2     public int search(int[] nums, int target) {
 3         return digui(nums,target,0,nums.length-1);
 4     }
 5     private int digui(int[] nums, int target, int low, int high){
 6         if ( low > high ) return -1;
 7         int mid = ( low + high ) / 2;
 8         if ( nums[mid] == target ) return mid;
 9         if ( nums[mid] < target )  return digui(nums,target,mid+1,high);
10         else return digui(nums,target,low,mid-1);
11     }
12 }

运行时间也是2ms。

Java jdk中已经内置好了二分查找的api：binarySearch(int[] a, int fromIndex, int toIndex, int key)；