이분 탐색

이분 탐색은 정렬되어있는 데이터에 대하여 진행한다
시간 복잡도: N개의 데이터가 있을때 O(logN)

아래 구현코드는 타깃을 찾거나 타깃이 삽입되어야 할 인덱스를 리턴한다.
**mid를구할때 비트 연산자로 구현하여 효율성을 높인다.

import java.io.*;
class Main {
  static int[] data={1,3,5,7,9,11,13,15,17,19};
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int target = Integer.parseInt(br.readLine());
    int res=binarySearch(0, data.length-1, target);
    System.out.println(res);
  }
  public static int binarySearch(int start,int end,int target){
    /*
    찾는 값과 일치하는 index 혹은 찾는 값이 들어가야할 인덱스 반환
    */
    if(start>end) return -1;
    int left=start, right=end;
    while(left<=right){
      if(left ==right){
        if(data[right]>=target) return right; // 끝점에 target이 있거나 끝점 보다 작은 경우
        else return right+1; // 찾는 범위가 데이터 밖인 경우
      }
      int mid =(left+right) >>1;
      if(data[mid]>target) right= mid;
      else if(data[mid]==target){
        return mid;
      }else{
        left=mid+1;
      }
    }
    return right;
  }
}