Binary_Search 이진탐색

분할 정복 알고리즘의 형태를 띈다

• 재귀를 주로 사용
• 리스트를 divide하면서 반복

구현

binary_search(list, find_data)

• list : 데이터 리스트
• find_data : 원하는 값
• 진행
  • list의 중간값을 find_data와 비교
    작으면 맨앞부터 중간값까지 중에서 중간값을 비교
    크면 중간값부터 맨끝까지 중에서 중간값을 비교
    이후 계속 반복

int[] array = new int[10];
Random rand = new Random();
for (int i = 0; i < array.length; i++)
	array[i] = rand.nextInt(10);

Arrays.sort(array);
System.out.println(binary_search(array, 1));

private static boolean binary_search(int[] list, int data){
	int mid;
	Arrays.stream(list).forEach(a -> System.out.print(a+" "));
	System.out.println();
	if (list.length > 1) {
		mid = list.length / 2;

		if (list[mid] == data)
			return true;
		else if (list[mid] < data)
			return binary_search(Arrays.copyOfRange(list, mid, list.length), data);
		else
			return binary_search(Arrays.copyOfRange(list, 0, mid), data);
	}
	else if (list.length == 1 && list[0] == data)
		return true;
	else if (list.length == 1 && list[0] != data)
		return false;
	else
		return false;
}
// 출력 - 반씩 줄어들면서 값을 찾는 모습이다
0 0 1 2 3 3 5 6 6 7 
0 0 1 2 3 
true

Sequential Search 순차탐색

순차탐색

• 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법
• 브루트포스 알고리즘 방식

int[] arr = new int[10];
Random rand = new Random();
for (int i = 0; i < arr.length; i++)
	arr[i] = rand.nextInt(10);
System.out.println(find_pos(arr, 5));

private static int find_pos(int[] arr, int data){
	//임의의 리스트에서 원하는 데이터의 위치를 리턴하는 알고리즘 작성

	Arrays.stream(arr).forEach(s -> System.out.print(s+" "));
	System.out.println();
	for (int i = 0; i < arr.length; i++)
		if (arr[i] == data)
			return i;

	return -1;
}