๊ฒ์ํ๋ ๋ฐฉ๋ฒ์ค ๊ฐ์ฅ ๊ธฐ๋ณธ์ ์ด๋ฉฐ ์์ฃผ ์ฌ์ฉํ๋ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ์๊ณ ๋ฆฌ์ฆ์ ์ฒ์ ํ์ตํ๋ค๋ฉด ํ์๋ก ์์์ผ ํ๋ค.
์ ํ ๊ฒ์
์๊ณ ๋ฆฌ์ฆ ์ ์
์ ํ ๊ฒ์์ด๋ ์์๊ฐ ์ง์ ๋ชจ์์ผ๋ก ๋์ด์ ๋ฐฐ์ด์์ ์ํ๋ ๊ฐ์ ์ฐพ๊ธฐ ์ํด 0๋ฒ์งธ index์์ ๋ถํฐ ๋ฐฐ์ด์ ๋๊น์ง ์์ฐจ์ ์ผ๋ก index๋ฅผ ๋น๊ตํ์ฌ ๊ฐ์ ์ฐพ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
์ข ๋ฃ ์กฐ๊ฑด
- ์กฐ๊ฑด 1 : ๊ฒ์ํ ๊ฐ์ ๋ฐ๊ฒฌํ์ง ๋ชปํ๊ณ ๋ฐฐ์ด์ ๋์ ์ง๋๊ฐ ๊ฒฝ์ฐ
- ์กฐ๊ฑด 2 : ๊ฒ์ํ ๊ฐ๊ณผ ๊ฐ์ ์์๋ฅผ ๋ฐ๊ฒฌํ ๊ฒฝ์ฐ
์๊ฐ ๋ณต์ก๋
์
๋ ฅ ๋ฐฐ์ด์ ๊ธธ์ด๊ฐ n ์ธ ๊ฒฝ์ฐ n/2
์์ค ์ฝ๋
์คํ ๊ฒฐ๊ณผ
์ ํ ๊ฒ์์ ๋ณด์ด๋ฒ
์ ํ ๊ฒ์์ ๋ฐ๋ณตํ ๋ ๋ง๋ค ์ข ๋ฃ ์กฐ๊ฑด์ ๋ชจ๋ ๊ฒ์ฌํ๋ค. ํ์ง๋ง ์ด ๋น์ฉ์ ์ ๋ฐ์ผ๋ก ์ค์ผ ์ ์๋ ๋ฐฉ๋ฒ์ด ๋ฐ๋ก ์ ํ๊ฒ์์ ๋ณด์ด๋ฒ์ด๋ผ๊ณ ํ๋ค.
๋ณด์ด๋ฒ์ arr[0] ~ arr[5]
๊น์ง ์๋ ๋ฐฐ์ด์ ๋ฐ์๋ค์ด๋ฉด ์์์ ์ผ๋ก ๋ฐฐ์ด์ ์นธ ์๋ฅผ 1์นธ ๋๋ ค ์ ์ผ ๋ง์ง๋ง ์ธ๋ฑ์ค์ ๊ฒ์์ ์ํ๋ key ๊ฐ์ ์ฝ์
ํ์ฌ ์ข
๋ฃ ์กฐ๊ฑด ์ค ์ข
๋ฃ ์กฐ๊ฑด 1 : ๊ฒ์ํ ๊ฐ์ ๋ฐ๊ฒฌํ์ง ๋ชปํ๊ณ ๋ฐฐ์ด์ ๋์ ์ง๋๊ฐ ๊ฒฝ์ฐ
์ ์กฐ๊ฑด ๊ฒ์ฌ ๋น์ฉ์ ์ค์ด๋ ๋ฐฉ๋ฒ์ ์ฌ์ฉํ๋ค.
์ข ๋ฃ ์กฐ๊ฑด์ ๋ค์ ๋ณด์.
์ ํ ๊ฒ์์ ์ข ๋ฃ ์กฐ๊ฑด
- ์กฐ๊ฑด 1 : ๊ฒ์ํ ๊ฐ์ ๋ฐ๊ฒฌํ์ง ๋ชปํ๊ณ ๋ฐฐ์ด์ ๋์ ์ง๋๊ฐ ๊ฒฝ์ฐ
- ์กฐ๊ฑด 2 : ๊ฒ์ํ ๊ฐ๊ณผ ๊ฐ์ ์์๋ฅผ ๋ฐ๊ฒฌํ ๊ฒฝ์ฐ
์ฌ๊ธฐ์ ์กฐ๊ฑด 1์ ์์ ๊ณ ์กฐ๊ฑด 2๋ก๋ง ์ข ๋ฃ๋ฅผ ํ์ํ ์ ์๊ฒ ํ๋ค.
์ ํ ๊ฒ์ ๋ณด์ด๋ฒ์ ์ข ๋ฃ ์กฐ๊ฑด
- ์กฐ๊ฑด 1 : ๊ฒ์ํ ๊ฐ๊ณผ ๊ฐ์ ์์๋ฅผ ๋ฐ๊ฒฌํ ๊ฒฝ์ฐ
์์ค ์ฝ๋
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int num = input.nextInt(); // ์์ ์
int[] x = new int[num+1];
for (int i = 0; i < num; i++) {
x[i] = input.nextInt();
}
int key = input.nextInt();
int ans = Sentry.sentry(x, num, key);
if(ans == -1) System.out.println("์์๊ฐ ์กด์ฌํ์ง ์์ต๋๋ค.");
else System.out.println(key+"๋" + "arr[" + ans +"] ์ ์์ต๋๋ค.");
}
}
class Sentry {
static int sentry(int[] arr, int num, int key){
int i = 0;
arr[num] = key;
while(true) {
if(arr[i] == key) break;
i++;
}
return i == num ? -1 : i;
}
}
๋๊ธ