이진검색 (Binary Search)

 

소스 구현 (정렬된 수에서 32를 찾기)

package org.kyhslam.algo;

public class binarySearch {

    static int a[] = {12,23,32,57,65,81,89,99};

    public static void main(String[] args) {

        viewArray(a);

        int target = 32;

        System.out.println();
        binary(target);
    }

    //반복문
    static public void binary(int target){

        int left = 0;
        int right= a.length-1; // 7

        while(left <= right){
            int mid = (left + right) / 2;

            if(a[mid] == target){
                System.out.println(mid+1);
                break;
            }else if(a[mid] > target){
                right = mid -1;
            }else if(a[mid] < target){
                left = mid +1;
            }
        }
        System.out.println("end");
    }


    static public void viewArray(int array[]){
        for(int i=0; i < array.length; i++){
            System.out.printf(array[i] + " ");
        }
    }

}

## 결과
12 23 32 57 65 81 89 99 
3
end

 

 

재귀함수로 구현

public static int binary_recur(int arr[], int start, int end, int target){
        int result = -1;
        int middle = 0;

        if (start <= end) {
            middle = (start+end)/2;

            if(target == arr[middle]){
                result = middle;
            }else if(target > arr[middle]){
                //start = middle + 1;
                result = binary_recur(arr, middle + 1, end, target);
            }else if(target < arr[middle]){
                //end = middle - 1;
                result = binary_recur(arr, start, middle - 1, target);
            }
        }

        return result;
    }

파이썬으로 구현

def binary_search(arr, x):
    left = 0;
    right = len(arr)

    while left <= right:
        mid = (left + right) // 2

        if x == arr[mid]:
            return mid
        elif x < arr[mid]:
            right = mid - 1
        else:
            left = mid + 1
    return -1

a = [1,4,9,16,25,36,49,64,81]
print(binary_search(a, 36))