leetcode 704(Binary Search) - java

문제

오름차순으로 정렬 된 정수 배열과 정수가 주어지면 검색 하는 함수 작성.
있는 경우 해당 인덱스를 반환, 그렇지 않으면 -1을 반환한다.
런타임 복잡성이 있는 알고리즘을 작성해야 함. O(log n)

주어진 배열에 targer 값이 있으면 그 위치의 인덱스를 반환, 없으면 -1을 반환하는 문제다.

예시1

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

예시2

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

제약 조건

1 <= nums.length <= 104

-104 < nums[i], target < 104

nums의 모든 정수는 고유합니다

nums는 오름차순으로 정렬됩니다.

풀이

class Solution {
    public int search(int[] nums, int target) {
        int high, low, middle;

        high = nums.length-1;
        low = 0;
        middle = (high + low) / 2;


        while(high >= low) {
            middle = (high + low) / 2;

            if(nums[middle] == target) {
                return middle;
            }
            if(nums[middle] > target) {
                high = middle-1;
            }
            if(nums[middle] < target) {
                low = middle + 1;
            }
        }
        return -1;
    }   
}