Description

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:

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

Example 2:

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

Constraints:

  • 1 <= nums.length <= 10^4
  • -10^4 < nums[i], target < 10^4
  • All the integers in nums are unique.
  • nums is sorted in ascending order.

Solution

Because the problem asks to solve this problem with time complexity of O(log n), it is a clear indication that we should use binary search algorithm.

 1class Solution {
 2    public int search(int[] nums, int target) {
 3        int left = 0;
 4        int right = nums.length - 1;
 5        int mid = 0;
 6
 7        while (left <= right) {
 8            mid = left + (right - left) / 2;
 9
10            if (nums[mid] > target) {
11                right = mid - 1;
12            } else if (nums[mid] < target) {
13                left = mid + 1;
14            } else {
15                return mid;
16            }
17        }
18        return -1;
19    }
20}
  • Time Complexity: O(log n)
  • Space Complexity: O(1)