[알고리즘]BinarySearch

BinarySearch(Recursive)

✍️size가 n인 정렬된 array S에서 K가 있는지 찾기

sorted array S[0..,n-1] , key k

k >= 0

S=[10,12,13,14,18,20,25] and k=18

먼저 S를 반으로 쪼갠다.
key인 18은 14보다 크므로 14보다 큰 곳의 배열만 찾으면 된다.
[14,18,20,25] 중에서 중간 값인 18이 찾으려는 값이므로 값을 찾았다.

이것을 한번 코드로 구현해보자.
java로 한번 구현 해보았다.

class Main {
  public static void main(String[] args) {
    int[] arr= {1,2,3,4,5,6,7,8,9,10};
    BS bs = new BS();
    System.out.println("find key: "+bs.BinarySearch(arr,0,9,9));
  }
}

class BS{
  int start;
  int end;
  int arr[];
  int key;
  int cnt = 0; // 몇번에 걸쳐 key를 찾았는지
  
  BS(){ 
  }

  int BinarySearch(int A[],int start,int end,int key){
    int mid = (start+end)/2;
    cnt ++;
    
    System.out.println("start:"+start);
    System.out.println("end:"+end);
    System.out.println("mid:"+mid);
    
    //mid가 key 값과 같으면 return
    if(A[mid] == key){
      System.out.println("cnt:"+cnt);
      return key;
    }
    // mid를 기준으로 반으로 배열을 자른뒤 조건에 맞는 배열을 찾는다.
    else if(key < A[mid]){ 
      return BinarySearch(A,start,mid-1,key);
     }
      
    else  return BinarySearch(A,mid+1,end,key);

    
  }
  
}

결과:
start:0
end:9
mid:4
start:5
end:9
mid:7
start:8
end:9
mid:8
cnt:3
find key: 9

time complexity = O(log n)이다.