Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

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

<解題>用二元搜尋法找到目標值

1.先比較數列中間值與目標值，若相等則回傳中間值的索引。 2.若中間值大於目標值，搜尋從左半部分(前半)。 3.若中間值小於目標值，搜尋從右半部分(後半)。

class Solution {
    public int search(int[] nums, int target) {
        int index = -1;
        int begin = 0, end = nums.length - 1, middle = (end + begin) / 2;
        
        while (begin <= end) {
            if (nums[middle] == target) {
                return middle;
            } else if (nums[middle] > target) {
                end = middle - 1;
            } else if (nums[middle] < target) {
                begin = middle + 1;
            }
            middle = (end + begin) / 2;
        }
        
        return index;
    }
}

可以和35. Search Insert Position做比較