2분 찾기 (반복)

1144 단어 반복 및 검색
1. 질문 설명:
정렬된 정형 수조와 주어진 숫자를 주고, 주어진 숫자보다 조금 큰 그 위치를 찾아라. 만약 되돌아오는 것을 찾지 못한다면-1
2. 사고방식 분석:
① 제목에서 우리는 수조가 순서를 정하는 것을 알 수 있다. 그러면 우리는 2분 검색을 통해 이 위치를 찾을 수 있다. 귀속 방법에서 우리가 전송해야 하는 매개 변수는 수조의 이미 알고 있는 수조, 시작 위치, 끝 위치, 그리고 주어진 목표 숫자가 있다.
② 귀속의 주체 방법에서 우리는 먼저 수조의 중간 위치를 풀어야 한다. 만약에 목표 숫자가 이 위치의 숫자보다 크다면 중간 위치 이후에 찾아야 한다. 그렇지 않으면 시작 위치에서 중간 위치로 찾아야 한다
③ 출구의 디자인은 끝 위치와 실제 위치가 같을 때 시작 위치의 값과 목표 숫자의 값을 판단하고 목표 숫자보다 크면 시작 위치를 되돌려주면 된다. 그렇지 않으면 끝 위치를 되돌려준다.
2분 찾기는 수조의 질서정연한 상황에 적합하다
3. 구체적인 코드는 다음과 같다.
public class Main {
	public static void main(String[] args) {
		int arr[] = {1, 5, 11, 24, 25, 32, 32, 32, 33};
		System.out.println(solve(arr, 32));
	}
	
	public static int solve(int arr[], int x){
		// x 
		//return x 
		if(x >= arr[arr.length - 1])	return -1;
		return solve(arr, 0, arr.length, x);
	}

	
	private static int solve(int[] arr, int begin, int end, int x) {
		if(end - begin == 1){
			if(arr[begin] > x){
				return begin;
			}
			return end;
		}
		int k = (begin + end) / 2;
		if(x >= arr[k]) return solve(arr, k, end, x);
		return solve(arr, begin, k, x);
	}
}

좋은 웹페이지 즐겨찾기