내가 찾고자 하는 데이터를 탐색하는 방법이라고 한다.
그냥 win+R하면 찾을 수 있는데..
엘런 튜링 아저씨 감사합니다~
개념
- 배열이 정렬되어 있어야 함
- 중간값(mid)을 기준으로 함
- 찾고자 하는 값(target)이 중간값보다 크다면, 탐색 종료
- target이 중간값보다 작다면 왼쪽 범위만 탐색
- target이 중간값보다 크다면 오른쪽 범위만 탐색
- 위 과정을 반복하며 탐색 범위를 좁혀감
내가 서랍에서 가위 찾을 때 이렇게 찾는데..
가위는 꼭 필요할 때 없는 것 같다.
퀵 정렬같은 건가?
퀵 정렬도 양방향에서 스캔했던 것 같은데..
코드 구현
import java.io.*;
import java.util.*;
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1; //가장 뒤의 index 값
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;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] inputData = br.readLine().split(" ");
int[] arr = new int[inputData.length];
for (int i = 0; i < inputData.length; i++) {
arr[i] = Integer.parseInt(inputData[i]);
}
// 정렬을 보장할 수 없다면, 정렬을 해주고 search할 수 있도록
int target = Integer.parseInt(br.readLine());
int index = binarySearch(arr, target); // -1이 오면 꺼지라함
System.out.println("찾고자 한 값, " + target + "의 위치는 " +
(index == -1
? "존재하지 않는다"
: (index + "에 있다.")));
}
}생각보다 간단..? 해서 당황스러웠다.
index 개념만 제대로 알고 있으면 "왼쪽에서부터 찾아", "오른쪽에서부터 찾아"라는 말을 이렇게 간단하게 표현할 수 있구나.
int left = 0, right = arr.length -1;
while (left <= right) {
int mid = (left + right) / 2;이 부분이 너무 신기하다.
left right를 지정해준 뒤에 mid를 넣어주고
if(arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid +1;
else right = mid - 1;mid가 target보다 작으면, mid의 좌측에 존재하는 값들을 전부 무시해버리고 오른쪽으로 이동하고,
아닐 경우(mid가 target보다 큰 경우)에는 반대로 우측에 존재하는 값을 전부 무시하고 왼쪽으로 이동한다!
신기하다
역시 컴퓨터는 숫자로 아주그냥 줄넘기를 해대는 구나.
1분 질의
이진 탐색을 배열로 하는 것과 리스트로 하는 것의 차이에 대해서 설명해주세요
LinkedList로 탐색할 경우, 데이터가 정렬되어 있는가 아닌가의 여부와 상관없이 순차 탐색을 하게 되며, 시간복잡도는 O(n)으로 올라가게 된다.
이는 데이터가 정렬되어있을 때에는 압도적으로 비효율적인 방법이다.
LinkedList는 탐색이 아닌, 데이터의 삽입/삭제의 경우에 유리하다.
반면에 이진탐색은 인덱스를 절반으로 나누어 빠르게 접근하는 과정을 가져, O(log N)의 속도로 처리 가능하다. 정렬되어 있기만 하다면 데이터의 양이 제아무리 방대하더라도 부담이 없다.
리스트더라도 ArrayList라면 이진 탐색이 가능하다.
