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:

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

 

题目理解：

给定一个递增数组，使用二分查找判断某一个数是否在数组中

解题思路：

二分查找是十分基础也十分重要的算法。

在本题当中，我们可以将二分查找理解为：将一个递增有序的数组分为三个部分，左边（left ~ mid-1），中间（mid），和右边（mid+1 ~ right）三个部分。如果mid的值大于要找的数target，那么target一定在左边部分，如果mid的值小于target，那么target一定在右边部分，如果target的值等于mid，那么mid就是我们要找的数。

确定的了target所在的部分之后，就可以继续对这一部分进行二分查找，直到找到target或者查找区域中已经没有数字了。

class Solution {
    public int search(int[] nums, int target) {
        int len = nums.length;
        int left = 0, right = len - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target)
                left = mid + 1;
            else if(nums[mid] > target)
                right = mid - 1;
            else
                return mid;
        }
        return -1;
    }
}