Java์ ์ ํ ๊ฒ์์ ํญ์ ๋ฐฐ์ด์์ ์์๋ฅผ ์ฐพ๋ ๋ฐฉ๋ฒ์ด์์ต๋๋ค. ๋ฐฐ์ด์ ๊ฐ ์์๋ฅผ ์์ฐจ์ ์ผ๋ก ๊ฒ์ํ๋ฉฐ ๊ตฌํํ๊ธฐ๊ฐ ๋งค์ฐ ์ฝ์ต๋๋ค. ๊ทธ๋ฌ๋ ์ ํ ๊ฒ์์ ๋จ์ ์ ๋ฌธ์ ์ ๋ฐฐ์ด์ ์๋ง ๊ฐ์ ์์๊ฐ ํฌํจ๋์ด ์์ ๋ ๋ช
๋ฐฑํฉ๋๋ค. ์ด๋ฌํ ๊ฒฝ์ฐ ์ด์ง ๊ฒ์์ ์ํด ๊ตฌํ๋ "๋ถํ ๋ฐ ์ ๋ณต" ๋ฐฉ๋ฒ์ ์๊ฐ ๋ฐ ๊ณต๊ฐ ๋ณต์ก์ฑ์ ์ผ๋์ ๋ ํ๋ก๊ทธ๋๋จธ์๊ฒ ํจ์ฌ ๋ ํจ์จ์ ์ด๊ณ ๋ฐ๋์งํฉ๋๋ค.
์ด์ง ๊ฒ์
์ด์ง ๊ฒ์์์๋ ํค(๊ฒ์ ์ค์ธ ์์)๋ฅผ ์ฐพ์ ๋๊น์ง ๋ฐฐ์ด์ ๋ ๋ถ๋ถ์ผ๋ก ๋ฐ๋ณตํด์ ๋๋๋๋ค. ๋ถํ ์ ๊ฐ์์
๋๋ค. ์ฆ, ๋ฐ์ดํฐ์ ๋ฌด๊ฒฐ์ฑ์ด ์ ์ง๋ฉ๋๋ค. ๋ฐ๋ณตํ ๋๋ง๋ค ๋ฐฐ์ด์ ์ค๊ฐ ๊ฐ์ ์ด์ ์ด ๋ง์ถฐ์ง๋๋ค. ๊ฐ์ด ์ฐพ๊ณ ์๋ ํค์ ๊ฐ์ผ๋ฉด ๋ฃจํ ๋๋ ์ฌ๊ท ํจ์๊ฐ ์ข
๋ฃ๋ฉ๋๋ค. ๊ทธ๋ ์ง ์์ผ๋ฉด ๊ณ์ ๋ฐ๋ณต๋ฉ๋๋ค. ๊ฐ์ด๋ฐ ๊ฐ์ด ํค๋ณด๋ค ํฌ๋ฉด ํจ์๋ ๋ฐฐ์ด์ ์ ๋ฐ๋ถ์ ์ด์ ์ ๋ง์ถ๊ณ ๊ทธ ๋ฐ๋๋ ๋ง์ฐฌ๊ฐ์ง์
๋๋ค. ์ด ํ๋ก์ธ์ค๋ ํค๋ฅผ ์ฐพ๊ฑฐ๋ ์ ์ฒด ๋ฐฐ์ด์ด ๋ฐ๋ณต๋ ๋๊น์ง ๋ฐ๋ณต๋ฉ๋๋ค.
์ ํ ๊ฒ์๊ณผ ์ด์ง ๊ฒ์์ ์ฐจ์ด์
์ ํ ๊ฒ์ |
์ด์ง ๊ฒ์ |
๋ฐฐ์ด์ ์์ฐจ์ ์ผ๋ก ๊ฒ์ |
๊ฐ์ ์ฐพ์ ๋๊น์ง ๋ฐฐ์ด์ ๋ ๋ถ๋ถ์ผ๋ก ๋๋๋๋ค. |
๋ชจ๋ ์ด๋ ์ด์์ ์๋ |
์ ๋ ฌ๋ ๋ฐฐ์ด์์๋ง ์๋ |
๋ณต์ก๋๋ O(N) |
๋ณต์ก๋๋ O(log2N) |
์ ๋ ฌ ๋ฐ ์ ๋ ฌ๋์ง ์์ ๋ฐฐ์ด์์ ์์
๊ฐ๋ฅ |
์ ๋ ฌ๋ ๋ฐฐ์ด์์๋ง ๊ตฌํํ ์ ์์ต๋๋ค. |
๋ ๋ณต์กํ ๊ตฌํ |
๊ตฌํ์ด ๋ ๋ณต์กํจ |
์ด์ง ๊ฒ์ ์๊ณ ๋ฆฌ์ฆ
์ด์ง ๊ฒ์ ์๊ณ ๋ฆฌ์ฆ์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
- ๋ฐฐ์ด์ ์ฒซ ๋ฒ์งธ ์ง์ ๊ณผ ๋ง์ง๋ง ์ง์ ์ ๊ฒฐ์ ํฉ๋๋ค. ํฌ์ธํธ๋ ๋ฐฐ์ด ๋ฐ ๊ฒ์ ์ค์ธ ํค์ ๋ฐ๋ผ ๊ฐ ๋ฐ๋ณต์์ ์กฐ์ ๋ฉ๋๋ค.
- ๋ฐฐ์ด์ ๋ฐ๋ณตํ๊ณ ํ์ฌ ์ฒซ ๋ฒ์งธ ํฌ์ธํธ์ ๋ง์ง๋ง ํฌ์ธํธ ์ฌ์ด์ ์ค๊ฐ ๊ฐ์ ๋น๊ตํฉ๋๋ค. ์ฒซ ๋ฒ์งธ ๋ฐ๋ณต์์ ์ฒซ ๋ฒ์งธ ๋ณ์์ ๋ง์ง๋ง ๋ณ์๋ ๋ฐฐ์ด์ ์ค์ ๋ณ์์ ๋์ผํฉ๋๋ค.
- ํค๊ฐ ์ค๊ฐ ๊ฐ๋ณด๋ค ํฌ๋ฉด ํด๋น ๊ฐ์ ์ธ๋ฑ์ค๊ฐ ์๋ก์ด "First" ๋ณ์์ ์ ์ฅ๋ฉ๋๋ค.
- ํค๊ฐ ์ค๊ฐ ๊ฐ๋ณด๋ค ์์ ๊ฒฝ์ฐ ํด๋น ๊ฐ์ ์ธ๋ฑ์ค๊ฐ 'Last' ๋ณ์์ ์ ์ฅ๋ฉ๋๋ค.
- ์ด ์กฐ๊ฑด์ ๋ค์ ๋ ์กฐ๊ฑด ์ค ํ๋๊ฐ ์ฐธ์ด ๋ ๋๊น์ง ๋ฐ๋ณต๋ฉ๋๋ค.
- ์ด์ ๊ฐ ๋ฐ๊ฒฌ๋์์ต๋๋ค.
- ์ ์ฒด ๋ฐฐ์ด์ด ๋ฐ๋ณต๋์์ต๋๋ค.
๋ฐ๋ณต ์ด์ง ๊ฒ์ ๋ฐ ์ฌ๊ท ์ด์ง ๊ฒ์์ ๋ํ ์ฝ๋๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
๋ฐ๋ณต ์ด์ง ๊ฒ์
๋ฐ๋ณต ๋ฐฉ๋ฒ์ ์ฌ์ฉํ ์ด์ง ๊ฒ์ ์ฝ๋๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
import java.util.Scanner;
public class IterativeBinarySearch {
public static void main(String[] args) {
int arr[] = {1,3,6,8,10};
System.out.println("Enter Number to Search For: ");
Scanner input = new Scanner (System.in);
int num = input.nextInt();
int result = BinarySearchIterative(arr,num);
if(result!=-1)
System.out.println("Value Found at Index #" + result);
else
System.out.println("Value Not Found");
}
public static int BinarySearchIterative(int[] arr, int num){
//Representing the Start and End Index After Division of Array
int start = 0;
int end = arr.length;
//Loop to Iterate Through the Array
for(int i = 0; iarr[n]){
start = n;
}
//If number to search for is greater than the arr value at index 'n'
else{
end = n;
}
}
//If number isn't found, return -1
return -1;
}
}
์ฌ๊ท ์ด์ง ๊ฒ์
์ฌ๊ท๋ฅผ ์ฌ์ฉํ๋ ์ด์ง ์ฝ๋๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
import java.util.Scanner;
public class RecursiveBinarySearch {
public static void main(String[] args) {
int arr[] = {1,3,6,8,10};
System.out.println("Enter Number to Search For: ");
Scanner input = new Scanner (System.in);
int num = input.nextInt();
int result = BinarySearchRecursive(arr,0,arr.length-1,num);
if(result!=-1)
System.out.println("Value Found at Index #" + result);
else
System.out.println("Value Not Found");
}
public static int BinarySearchRecursive(int arr[], int a, int b, int num){
//Base Case to Exit the Recursive Function
if (b < 1) {
return -1;
}
int n = a + (b=1)/2;
//If number is found at mean index of start and end
if(arr[n]==num)
return n;
//If number to search for is greater than the arr value at index 'n'
else if(arr[n]>num)
return BinarySearchRecursive(arr,a,n-1,num);
//If number to search for is greater than the arr value at index 'n'
else
return BinarySearchRecursive(arr,n+1,b,num);
}
}
์๊ฐ ๋ณต์ก๋
ํต๊ณผํ๋ ๋ฐ๋ณต๋ง๋ค ๋ฐฐ์ด, ์ฆ ๊ฒ์ ๊ณต๊ฐ์ด ๋ฐ์ผ๋ก ๋๋ฉ๋๋ค. ๋งค ๋ฐ๋ณต 'm' ํ์ ๊ฒ์ ๊ณต๊ฐ์ N/2m ํฌ๊ธฐ๋ก ๋ณ๊ฒฝ๋ฉ๋๋ค. ์ต์
์ ์๋๋ฆฌ์ค์์๋ ๋ฐฐ์ด์ ๋ฐ๋์ชฝ์ ํ๋์ ์์๋ง ๋จ๊ฒ ๋ฉ๋๋ค. ์ด๋ ์ด์ง ๊ฒ์์ ๋ณต์ก๋๋ k = log2N์ด ๋ฉ๋๋ค. ์ ํ ๊ฒ์์ ์๊ฐ ๋ณต์ก๋๋ O(N)์ด๋ฏ๋ก ์ด์ง ๊ฒ์์ด O(log2N) ๋ณต์ก๋๋ก ํจ์ฌ ๋นจ๋ผ์ง๋๋ค. ์ด๊ฒ์ด ์ ํ ๊ฒ์๋ณด๋ค ์ด์ง ๊ฒ์์ ์ฌ์ฉํ๋ ์ฃผ์ ์ด์ ์
๋๋ค.
๊ณต๊ฐ ๋ณต์ก์ฑ
์ด์ง ๊ฒ์์ start, end ๋ฐ mid์ ์ธ ๊ฐ์ง ๋ณ์๋ฅผ ์ฌ์ฉํฉ๋๋ค. ์ด ์ธ ๋ณ์๋ ๋ฐฐ์ด ์ธ๋ฑ์ค์ ๋ฉ๋ชจ๋ฆฌ ์์น๋ฅผ ๊ฐ๋ฆฌํค๋ ํฌ์ธํฐ๋ก ์์ฑ๋ฉ๋๋ค. ์ด๋ก ์ธํด ์ด์ง ๊ฒ์์ ๊ณต๊ฐ์ ๋ํด ๋งค์ฐ ํจ์จ์ ์
๋๋ค. ๋ฐ๋ณต ์ด์ง ๊ฒ์์ ๊ณต๊ฐ ๋ณต์ก๋๋ O(1)์
๋๋ค. ์ฌ๊ท ๊ตฌํ์ ๊ฒฝ์ฐ O(log N)์
๋๋ค.
GO TO FULL VERSION