이진탐색 알고리즘

어떤값을 찾을때 (탐색할때) 정렬의특징을 이용해 빨리 찾을수있음을 이용.
정렬되어있을경우, 어떤 값을 찾을 때:O(N) - >O(lgN)

다른방법으로 풀다가 시간복잡도가 초과된다면 이용

예시: 1234 숫자중에 3을 찾을경우
for문으로 전체 비교해서 3을 찾는다.
but 이진탐색은 반을 잘라서 비교후 계속 잘라서 비교하는 알고리즘 전체를 찾는 것이아님.

핵심코드(꼭 외워야함):

//시작점 ,끝나는점, 찾고자 하는 수
void search(int st,int en,int target){
	// 시작점 종료점이 같아질때 값이 target과 	같은지 비교
    if(st == en){
    	if(nums[st] == target){
        	return x
        }
        else return x
    }
    // 중간지점을 정수값으로 구해준다
    int mid = (st + en) / 2;
    //만약 target값이 mid 값보다 크다면 정렬된 수의 중간값보다 크다는 것이기 때문에 중간값보
    //다 오른 쪽에 있다는 뜻, 아니면 왼쪽에 
    if(nums[mid] < target){
    	search(mid + 1,en , target);
    }else{
    	search(st, mid, target);
    }
}