소스 파일명 : code_1.src
001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
/* (2019.2.11, 차재복, Cha Jae Bok, cjbword@gmail.com) */

/** 이진 검색 **/

// [일상언어]
/*
    ① 먼저 상한(high),하한(low)을 정함
    ② 최초 하한은 배열의 첫째값, 상한은 배열의 끝값
    ③ 상한,하한 사이에 중간값을 찾는 루프
        ⓐ 중간값 지정 (상한,하한의 가운데)
        ⓑ 찾던 값이 중간값 보다 큰지 작은지에 따라, 하한 또는 상한을 재지정
        ⓒ 찾던 값이 중간값 이면, 검색 끝냄
    ④ 상한,하한 구간을 줄여가는 중에 역전되면, 이 배열에 찾는 값이 없는 것임
*/

// [C]
int binary_search(int key, int arr[], int length) {
    int low, high, mid;
    low = 0;
    high = length - 1;
    while (low <= high) {
        mid = (low + high)/2;
        if (key < arr[mid]) high = mid - 1;
        else if (key > arr[mid]) low = mid +1;
        else return mid;
    }
    return -1;
}

// [Java]
public static int binarySearch(int key, int[] arr) {
    int low = 0;
    int high = arr.length - 1;
    while (low <= high) {
        int mid = low + (high - low)/2;
        if (key < arr[mid]) high = mid - 1;
        else if (key > arr[mid]) low = mid + 1;
        else return mid;
    }
    return false;
}

// <참고사항>
/*
ㅇ C 언어는, 배열 길이를 속성화시켜 취급 안하므로, 함수 인수로 넘겨주어야 함
ㅇ (high-low)/2 : 실수(큰그릇)->정수(작은그릇)로 형변환시 소수점 이하 절삭
ㅇ `mid = (low + high)/2` 및 `mid = low + (high - low)/2`은 같음
*/