Binary Search (이진검색)

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 <= 104
• -104 < nums[i], target < 104
• All the integers in nums are unique.
• nums is sorted in ascending order.

 

---

 

 

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

 

---

 

처음 접해본 알고리즘 문제. 처음이라 그런지 어떻게 풀어야 할지 감도 오지 않았다. 기본적인 개념은 전체 배열을 절반으로 쪼개가면서 조회해야 할 선택지(배열의 구성요소)를 줄여나간다는 데 있다. 배열을 쪼갤 때는 쪼갤 기준이 존재해야 한다. 여기서는 변수 pivot을 중심값이 되는 기준으로 한다.

 

처음에는 배열의 전체 길이에서 배열의 첫째 값을 뺀다.