기억하고싶은것들

A peak element is an element that is strictly greater than its neighbors.

Given an integer array nums, find a peak element, and return its index.

If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞.

You must write an algorithm that runs in O(log n) time.

"peak"는 양 옆의 숫자들보다 큰 경우를 말한다.

integer 배열 nums가 주어진다, 해당 배열에서 peak을 찾고 그 인덱스를 반환하라.

만약 배열에 여러게의 peak이 존재한다면, 어떠한 인덱스를 반환해도 된다.

배열 밖의 범위의 요소는 가장 작은 수로 인지하라 ( 즉, 맨 처음, 맨 뒤 인덱스의 값은 바로 옆 하나의 이웃보다 크면 peak이 된다)

반드시 시간 복잡도가 O(log n) 인 알고리즘을 작성하라.

배열의 search 알고리즘 문제의 시간 복잡도가 O(log n) 를 만족하기 위해서는 Binary Search를 사용해야 한다. 

결국 peak은 배열의 가장 큰 숫자를 찾으면 된다. 가장 크기 때문에 양옆의 숫자들보다 크기 때문이다.

배열의 가장 큰 숫자를 binary search로 찾는 문제로 생각하고 풀어보자.

    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (right > left) { // binary search 
            int pivot = (left + right) / 2;
            if (nums[pivot] < nums[pivot + 1]) {
                left = pivot + 1;
            } else {
                right = pivot;
            }
        }
        return right;
    }

문제출처 : 

https://leetcode.com/problems/find-peak-element/

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

오름차순으로 정렬된 integer 배열과 타깃 integer가 주어진 상황에서 

타깃을 배열에서 찾는 코드를 작성하여라

타깃이 존재한다면 해당 숫자가 들어있는 배열의 인덱스를 반환하고, 없다면 -1을 반환하라

반드시 시간 복잡도가 O(log n)인 알고리즘으로 작성하라

정렬된 배열에서 값을 찾는 문제로 시간 복잡도가 O(log n)인 알고리즘을 사용해야 한다. 

Binary Search를 이용하여 문제를 해결하도록 하자.

    public int search(int[] nums, int target) {

        int left = 0;
        int right = nums.length - 1;
        int pivot = 0;

        while (left <= right) {
            pivot = (left + right) / 2;

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

먼저 left, right 인덱스를 지정하고,

해당 인덱스들을 기반으로 while loop의 조건을 지정한다.

Binary Search의 경우에는 left 인덱스가 right 인덱스보다 큰 경우에는 타깃으로 하는 값이 없는 경우이므로 해당 조건이 while loop에 들어가게 된다. 

Binary Search에서는 각각의 left, right 인덱스의 중간값을 pivot으로 설정하고 

해당 값을 기준으로 다음 조건의 인덱스를 지정한다.

pivot 인덱스의 배열값이 타깃보다 작은 경우에는 left 인덱스를 pivot 다음 인덱스로 지정

pivot 인덱스의 배열값이 타깃보다 큰 경우에는 right 인덱스를 pivot 이전 인덱스로 지정

문제 출처

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