99클럽 코테 스터디 19일차 TIL + 오늘의 학습 키워드 이진탐색

- 오늘의 학습 키워드 이분 탐색
- 공부한 내용 본인의 언어로 정리하기

이분탐색 

입력받은 배열 A를 정렬-> 배열 B

각 질문 값에 대해서 lower bound 찾기

lower bound함수는 이분탐색을 사용해서 정렬된 배열에서 target 값 이상의 첫번째 위치를

찾음

모든 결과를 수집 반환

 

수도 코드

function solveSortMasterProblem(A, queries):
    1. 배열 A를 오름차순으로 정렬한다.
    2. 각 질문 D에 대해:
        a. D가 배열 A에서 처음 등장하는 위치를 이분 탐색으로 찾는다.
        b. 찾은 위치를 출력한다. 찾지 못했다면 -1을 출력한다.

function findFirstOccurrence(arr, target):
    1. 탐색 범위를 배열의 처음부터 끝까지로 설정한다.
    2. 결과값을 -1로 초기화한다.
    3. 탐색 범위가 유효한 동안:
        a. 중간 위치를 계산한다.
        b. 중간값이 target과 정확히 일치하면:
           - 현재 위치를 결과에 저장한다.
           - 더 앞에 같은 값이 있는지 확인하기 위해 왼쪽 부분만 계속 탐색한다.
        c. 중간값이 target보다 크면 왼쪽 부분을 탐색한다.
        d. 중간값이 target보다 작으면 오른쪽 부분을 탐색한다.
    4. 저장된 결과값을 반환한다.

- 오늘의 회고
  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지

문제 틀렸다.

lowerBound 함수에서 등호로 비교했는데 D에서 B가 처음으로 등장한 위치를 제대로 못찾았다.
  - 어떻게 해결했는지

target 값을 찾았을때

target 보다 arr[mid] 값이 더 클때 , 작을때 로 세분화하여 나눴다.

target 값이랑 mid가 같으면 현재 위치를 저장하고  right에서 동일한 값이 있는지를 찾고

만약 mid가 더 크면 right를 mid-1로 만들었다.
  - 무엇을 새롭게 알았는지

lower bound:  정렬된 배열에서 특정 값이상이 처음 나타나는 위치를 찾는 알고리즘

이분 탐색의 시간 복잡도가 O(logN) 인 이유: 

각 단계마다 탐색시간이 1/2 으로 줄어들기 때문이다.

 

이분 탐색에서 중간값 계산 공식 mid =left +(right-left)/2
  - 내일 학습할 것은 무엇인지