Binary Search

LeetCode 704번

Tags. Binary Search

 

https://leetcode.com/problems/binary-search/

Binary Search - LeetCode

문제

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].

 

 

Solution

class Solution {
    public int search(int[] nums, int target) {
        
        int upperBound = nums.length - 1;
        int lowerBound = 0;
        
        while(lowerBound <= upperBound) {
            double mid = (Math.floor((upperBound + lowerBound ) / 2));
            int mid2 = (int)(mid);
            if(nums[mid2] < target) {
                lowerBound = mid2 + 1;
            }else if(nums[mid2] > target) {
                upperBound = mid2 - 1;
            }else {
                return mid2;
            }
        }
        return -1;
    }
}

고찰

배열에 타겟이 존재한다면 해당 index값을 출력하기 위해 이진검색 형태로 구현하였다.

순차검색( Linear Search ) 보다 논리적으로는 2배 빠른 속도라고 한다.

 

정렬된 배열의 중간에 위치한 값과 target 값을 비교하여 while loop 한번당 배열의 길이를 절반씩 줄여서 해당하는 값을 찾아 내는 흐름

 

Runtime : 0ms

Memory : 38.8MB