[알고리즘] 이분탐색

int BinarySearch(int arr[], int target) {
	int left = 0;
    int right = arr.length-1;
    int mid;
    
    while(left<=right){
    	mid = (left+right) / 2;
        
        if(arr[mid] == target)
        	return mid;
        
        else if(arr[mid] > target)
        	right = mid-1;
        else
        	left = mid+1;
   	}
    return -1;
}

 

1. 내가 찾아야 할 범위를 left ~ right 로 설정한다.

2. 정답을 mid로 간주하고 유효한지 확인한다. 

3. 2를 따지며 left, right를 줄여나간다. (right = mid-1, left = mid+1)

4. left > right가 되면 종료한다.