이분법

  • 정렬된배열에서 특정 값을 찾을때 효율적이다.
    • 특정 값을 찾기
    • 특정값의 이상중에 최소인값

어떻게 생각하면 나을까

  • 대부분 a보다 크면서 최소인값을 구하라는 식의 문제가 있다고 생각해보자.
  • [1,3,5,7,9,11] 이런 배열이 존재할때 4보다 크면서 최소인값 찾기로 해보자.
  • 여기서 먼저 4보다 작은것들은 x, 크거나 같으면 o를 이용해표현해보면
    • [x,x,o,o,o,o]이런 식으로 o와 x로 생각해보자.
  • 왼쪽과 오른쪽 영역 어디를 선택할지
    • mid가 원하는 조건(a보다 큰값 = o의값)을 만족하면 왼쪽 영역을확인 right = mid-1
      • 왜냐? a보다 큰값에서 가장 작은 값을 찾아야 하기때문에 영역을 왼쪽을 확인한다.
    • mid가 원한느 조건에 만족안하면(x의 값) 오른쪽 영역 확인 left = mid+1
      • o가 나올때까지 오른쪽 영역을 확인하는 과정이다.
  • left와 right가 계속해서 최종적으로 만들어지는 모습을 생각해보자.
    • [x,x,x],[x,x,o], [x,o,o], [x,o], [o,o,o], [o,o] 이정도가 만들어질수있다
  • 여기서 후반가면 [x,x],[x,o],[o,o] 3가지 경우로 좁혀질것이다.
    • 이럴때 mid는 left의 위치와 같아지게 된다(left=0, right=1, mid => (0+1)/2 => 0.5 => 0 ). 하나하나 확인해보자.

[x,x]일때

  • index를 0,1로 생각해보자.
    • 초기는 left는 0, right는 1
  • mid((left+right)/2로 left와 right가 1차이면 mid는 left와 같다.)는 x이다, 그럼 오른쪽영역은 [x]를 left=mid+1로 간다.
    • 오른쪽 영역으로 갔기 때문에 left=1, right=1로 된다.
  • left와 right, mid가 전부 같아진다. 그런데 mid는 x이며 오른쪽영역을 자르기위해 left=mid+1로 left가 +1된다.
    • 다시 오른쪽 갔기 때문에 left=2, right=1이다.
  • 결국 left<=right라는 조건이 깨지게 되고 left가 원하는 결과값을 저장하고 있다!
    • left는 2를 저장하고 있다.

[x,o]일때

  • index를 0,1로 생각해보자.
    • 초기는 left는 0, right는 1
  • mid는 x이다. 그럼 오른쪽영역으로 left=mid+1로 잘라낸다.결국 [o]가 된다.
    • 오른쪽 영역으로 가서, left=1, right=1
  • left, right, mid는 전부 같으며, mid는 o로 조건을 만족한다. 그러면 왼쪽영역으로 right=mid-1로 right가 -1된다.
    • 왼쪽영역으로 가서 left=1, right=0이된다.
  • left<=right조건에서 빠져나오게 되고 left가 원한는 결과값을 저장하게 된다.
    • left는 1를 저장하고 있다.

[o,o]일때

  • index를 0,1로 생각해보자.
    • 초기는 left는 0, right는 1
  • mid는 o이다. 그럼 왼쪽영역으로 right = mid-1로 잘라낸다.결국 [o]가 된다.
    • 왼쪽영역으로 가서 left=0, right=0이된다.
  • left, right, mid는 전부 같으며, mid는 o로 조건을 만족한다. 그러면 왼쪽영역으로 right=mid-1로 right가 -1된다.
    • 왼쪽영역으로 가서 left=0, right=-1이 된다.
  • left<=right조건에서 빠져나오게 되고 left가 원한는 결과값을 저장하게 된다.
    • left는 0을 저장하고 있다.

코드

  //정렬된 b에서 a
  int a,int[] B;

  int left = 0;
  int right = B.length-1;

  //a보다 큰값의 시작 위치
  //가운데가 a보다 크면
      //right를 mid로
  //가운데가 a보다 작으면
      //left를 mid로
  //가운데와 a가 같으면
      //right를 mid로

  if(B[B.length-1]<a){
      return B.length;
  }
  if(a<=B[0]){
      return 0;
  }

  while(left<=right){
      int mid = (left+right)/2;
      if(B[mid]>=a){
          right = mid-1;
      }else{
          left = mid+1;
      }
  }


  return left;

풀어볼 문제