이진 탐색이란?
BinarySearch 라고 부르며, 정렬되어 있는 배열에서 특정 값을 찾는 알고리즘.
X 라는 숫자를 찾는다고 할 때, 배열의 중간값을 X 와 비교한다.
X 보다 중간값이 크면 X는 중간값 기준으로 배열의 왼쪽에 있고, X 보다 중간값이 작으면 X는 중간값 기준으로 오른쪽에 있다.
아래 배열 에서 40을 찾는다고 생각해보면
10 | 20 | 30 | 40 | 50 |
X = 40
mid = 30
X> mid 이기 때문에 X 는 mid기준으로 오른쪽
이런식으로 찾아 나간다.
코드로 보자면
public static int BinarySearch(int[]arr, int num)
{
int high = arr.length -1;
int low = 0;
int mid = 0;
while(low<=high)
{
mid = (high + low)/2;
if(arr[mid]==num)
{
return 1;
}else if(arr[mid]>num)
{
high=mid-1;
}else if(arr[mid]<num)
{
low=mid+1;
}
}
return 0;
}
Java
복사
mid 값을 이용해 X가 배열의 오른쪽에있는지 왼쪽에 있는지 찾고, 그 결과에 따라 high, mid값 을 조절해준다.