[LeetCode] 704 Binary Search

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:

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

Constraints:

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

---

풀이

• target이 nums에 존재하는지 확인 후 target의 index를 반환하는 문제이다. target이 nums에 존재하지 않는 경우 -1을 반환한다.

• 배열이 정렬된 경우 이진 탐색을 사용할 수 있다.

• 배열의 중앙 값을 pivot으로 설정한 후, target이 pivot보다 작으면 - target의 왼쪽에서 찾아보고, 크다면 target의 오른쪽에서 찾아본다.

  pivot과 target이 동일할 경우 pivot을 반환한다.
  pivot이 target보다 작을 경우 left를 pivot+1로 바꾼다.
  pivot이 target보다 클 경우 right를 pivot-1로 바꾼다.

• 이를 값을 찾을 때까지, 또는 left가 right보다 커질 때까지 반복한다.

---

코드

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int pivot;

        while (left <= right) {
            pivot = (left + right) / 2;
            if (nums[pivot] == target) {
                return pivot;
            } else if (nums[pivot] < target) {
                left = pivot + 1;
            } else {
                right = pivot - 1;
            }
        }
        return -1;
    }
}