Binary search

🎲

Binary search

Task

• Assume that we have n ≥ 1 distinct integers that are already sorted and stored in the array list

• For a given integer m, we want to know whether there is 1 such that list[i] = m

 

Input : a sorted array list[i], 0 ≤ i < n, an integer m

Output: i if list[i] = m, -1 if there is no such i

 

Specification

let left = 0, rigth = n - 1, middle = (left + rigth) / 2
1. If m < list[middle], then right = middle - 1
2. If m = list[middle], then return middle
3. If m > list[middle], then left = middle + 1
4. Recalcuate middle and repeat 1 ~ 3 while there is more integers to check

right와 left로 범위를 좁혀가면서 값을 찾는다

그러기 위해 중간 값을 정한 후 찾으려는 값과 중간 값을 비교한 뒤 범위를 조정한다

 

right < left 는 값이 없는 경우이므로 -1을 반환한다

 

: left
: middle
: right

 

m : 3

input으로 정렬된 배열을 넣어준다

3 4 5 6

middle : (0 + 3) / 2 = 1, left : 0, right : 3

m < 4 이므로 right = 1 -1 = 0이 된다

 

34 56

middle = (0 + 0) / 2 = 0이다

m == 0 이므로 0을 return한다!

 

My Code

int binary_search(int left, int right, int findN, int *list){
    int middle = (left + right) / 2;
    
    if(right < left)
        return -1;
    
    if(findN < list[middle])
        right = middle - 1;
    else if (findN > list[middle])
        left = middle + 1;
    else
        return middle;
        
    binary_search(left, right, findN, list);
}