이분 탐색(Binary Search)

이분 탐색

탐색 범위를 두 부분으로 분할하면서 찾는 방식

처음부터 끝까지 돌면서 탐색하는 것보다 훨씬 빠른 장점을 지님

전체 탐색의 O(N)에 비해 O(logN)의 효율성을 가진다.

과정

• 우선 정렬을 해야함
• left와 right을 통해 mid값을 설정
• mid와 내가 구하고자 하는 값을 비교
• 구할 값이 mid보다 높으면 : left = mid+1 구할 값이 mid보다 낮으면 : right = mid -1
• left > right가 될 때까지 계속 반복하기

코드

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 
        binarySearch(2, arr);
    }
 
    public static void binarySearch(int iKey, int arr[]) {
        int mid;
        int left = 0;
        int right = arr.length - 1;
 
        while (right >= left) {
            mid = (right + left) / 2;
 
            if (iKey == arr[mid]) {
                System.out.println(iKey + " is in the array with index value: " + mid);
                break;
            }
 
            if (iKey < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
 
        }
    }
}


출처: 

📝참고

https://gyoogle.dev/blog/algorithm/Binary%20Search.html
https://blog.opid.kr/489