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

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

연속된 버전이 있고 어떤 버전부터 나쁜 버전이 시작됨

나쁜 버전 이후의 모든 버전이 나쁘다

API 호출을 최소화 하면서 첫번째 나쁜 버전을 찾아야한다.

 

수도코드

function firstBadVersion(n);
  left =1
  right =n
  
  while left<right;
    mid =left+(right -left)/2
    
    if isBadVersion(mid);
      right=mid 
      else;
      left=mid+1
      
     return left

---

추가 공부 25.05.07

이진검색

①a[i] <key 일때:

key보다 작은것이 분명하면 검색 대상에서 제외

 

②a[i] >key 일때:

key보다 큰것이 분명하면 검색 대상에서 제외

이진검색은 검색을 반복할때마다 검색범위가 절반으로 줄어든다.

시간복잡도 log n

단 , 이진검색은 오름차순으로 정렬되어있음을 가정한다.

 

static <T> int binarySearch(T[] a, T key, Comparator<? super T>c )

 

T[] a : T 형 배열 

T key : T 형의 키값

Comparator<? super T> c : 대소 관계를 생성하기 위한 comparator

compare 메시더그 comparator 안에 들어있다.

int compare(T z1, T z2);
boolean equals(Object o);

 

이거 완전 까먹고 있었음

z1이 더 크면 양수

z1이 더 작으면 음수

z1==z2 이면 0

---

 

 

중간 버전이 나쁘면 isBadVersion(mid)==true

첫번째 나쁜 버전 mid 이하

right =mid로 오른쪽 범위를 줄인다

중간 버전이 좋으면 isBadVersion(min)==false

 첫번째 나쁜버전은 mid 이후

left =mid +1 로 왼쪽범위를 줄인다.

 

left>= right가 되면 반복을 종료

 

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

아직 미해결 이해를 못함 gpt로 써도 이해를 못하다니...

자료구조 추가 공부
  - 어떻게 해결했는지

자료구조 추가 공부
  - 무엇을 새롭게 알았는지

이진검색할때 기준값 key 보다 작거나 큰것으로 절반으로 나누어서 검색할 범위를 찾는다.

compare 메서드 사용법 다시 학습했다.

  - 내일 학습할 것은 무엇인지