[항해99]99클럽 코테 스터디 14일차 TIL + 이분탐색

 

 

1.  오늘의 학습 키워드 : 이분 탐색(Binary Search)

이진탐색이라고도 하는 이분탐색입니다.

 

- 이분 탐색

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

*정렬이 포인트!!

변수 3개(start, mid, end)를 사용해 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해 원하는 데이터를 찾는 것이 이분탐색의 과정

 

- 시간 복잡도

O(log N)

2.  오늘의 문제 :  Search Insert Positon

https://leetcode.com/problems/search-insert-position/

이진탐색의 아주아주 기본 문제입니다!!

3.  풀이 

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

처음에 오류가 나서... 왜이러지 이게 맞는데 하고보니까 while문에 left와 right를 반대로 쓴거있죠... 이렇게라도 오류를 고쳐 해결한 점에 아주 저 자신을 칭찬합니다!

3.  회고 

이진 탐색 얼마전에 알고리즘 강의를 들으며 풀었던 문젠데 금방 기억이 나지 않았어요... 하지만 이렇게 발전하다 보면 할 수 있겠죠? 오늘 클럽장님께서 모든 문제를 완전탐색으로 접급해보고 DP로 풀지 정한다고 하셨는데 시간 복잡도가 10억 이렇게 되면 이진 탐색을 도전한다고 하셔서 그 점 명심하고 코테 문제에 적용하려고 합니다. 

 

참고 사이트

https://jaime-note.tistory.com/161

[LeetCode - Daily Challenge] 35. Search Insert Position

이분은 코드뿐만아니라 테스트코드까지 작성해서 올려주셨더라구요. 자기주도프로젝트할 때 교수님께서 테스트코드 작성이 아주 중요하다 해서 보며 공부하는게 좋을 것 같아 가져왔습니다!

https://velog.io/@kwontae1313/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89Binary-Search-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%9C%EB%85%90

이진 탐색(Binary Search) 알고리즘 개념