이진탐색

이진탐색(BinarySearch)

---

• 정렬된 배열에서 타깃을 원하는 요소를 찾는 알고리즘
• 시간복잡도 O(logN)
• 이진탐색트리와 이름이 비슷하지만 이진탐색트리는 정렬된 요소를 저장하고 탐색하는 자료구조라면,
  이진탐색은 정렬된 배열에서 값을 찾아내는 알고리즘이다.

 

[이진탐색 과정]

1부터 100이 주어진 배열에서 77 찾기

• 1차 탐색

1

...

50

...

100

• 2차 탐색

50

...

75

...

100

• 3차 탐색

75

...

81

...

87

• 4차 탐색

75

...

78

...

81

• 5차 탐색

75

...

76

...

78

• 6차 탐색

76

...

77

...

78

 

[이진탐색 java 코드]

public static int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;

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

        if (arr[mid] == target)
            return mid; // 찾은 위치 반환
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return -1; // 찾지 못했을 경우
}