[이진탐색]

arr: 정렬된 상태

var start = 0;
var end = arr.length-1;

while (start <= end) {
    var mid = parseInt((start + end) /2);
    var midv = arr[mid];
    if (target < midv) {
        end = mid-1;
    } else if (midv < target) {
        start = mid+1;
    } else {
        answer = mid;
        break;
    }
}

parseInt는 소수점 버림이기 때문에

start <= mid < end

mid와 end는 절대로 같아 질 수 없음(단, 배열 길이가 1 보다 클때)

(배열 길이가 1 이면 start=mid=end긴 한데, while문 딱 한번 돌고 끝나버림)

 

1. mid-1 <= end,
   start <= end
2. start < mid,
   start <= mid -1 <= end
3. start = mid,
   end = mid-1 < start. 이 경우는 while밖으로 빠짐