binarysearch이진탐색이분탐색이라고 불리는 거 java로 만들어봐!

이진탐색을 자바로 만들어보자! 그 이전에 이진탐색이란?

다 탐색하기 힘드니까 반띵해서 찾아본다 이말이야. 

여기서 중요한 점은 배열이 꼭!!!!!! 정렬이 되어있어야되

아직 잘 모르겠다고 ? 내가 그림을 그려줄꼐 

배열의 크기가 6개인 배열에서 9를 찾는 그림이야.

배열의 처음과 끝의 중간인 2에서 부터 비교를 해 

 2의 값(4)이 9보다 작으니 low의 값을 mid+1로 옮겨야되

다음 상황이야 이번엔 mid(4)의 값이 7이지 아직도 9보다 작아 그럼 아까 했던 거 처럼 mid를 low로 바꾸고 (low+high)/2 +1 을 mid로 바꾸면 되 다음 상황을 보여줄께

찾았다! mid의 값이 찾던 9의 값이야 이렇게 되면 이진 탐색이 끝나게 되지 이 것을 내가 재귀함수로 짜봤어 잘봐

public static int search(int key, int low, int high, int[] arr) {
		
		if(low<=high) {
			int mid = (low+high)/2;
			
			if(key==arr[mid]) {
				return key;
			}
			else if(key>arr[mid]) {
				return search(key,mid+1,high,arr);
			}
			else {
				return search(key,low,mid-1,arr);
			}
		}
		return 0;
	}

low가 high랑 같아지거나 커질때 까지도 값을 못찾으면 그 배열엔 찾는 값이 없는거야 그래서 0을 리턴하지 

mid값에 +1 과 -1을 하는 이유가 있냐고? 바보야 mid는 벌써 비교해봤잖아 그럼 빼고 비교해야지 안그래?

 

다음엔 다른 탐색을 가져와볼께 안녕