This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
| algorithm:binary_search [2016/06/07 13:14] – 만듦 ledyx | algorithm:binary_search [2021/02/07 03:15] (current) – external edit 127.0.0.1 | ||
|---|---|---|---|
| Line 5: | Line 5: | ||
| {{tag> | {{tag> | ||
| - | * 일반적인 구현 | + | * 일반적 구현 |
| <sxh java> | <sxh java> | ||
| public static int binarySearch(int[] arr, int target) { | public static int binarySearch(int[] arr, int target) { | ||
| Line 45: | Line 45: | ||
| - | * A ＜ X ≤ B 조건을 검색. (반환값이 index+1 이므로) | + | == Interpolation Search (보간 탐색) == |
| - | <sxh java> | + | 중간부터 찾지 말고, 실제 값이 있는 위치부터 찾기! |
| - | public static int binarySearch(ArrayList< | + | |
| + | * 일반적 구현 | ||
| + | <sxh java ; highlight: | ||
| + | public static int interpolationSearch(int[] arr, int target) { | ||
| int left = 0; | int left = 0; | ||
| - | int right = list.size() | + | int right = arr.length |
| - | int middle | + | int mid = 0; |
| + | |||
| + | int count = 0; | ||
| while(left <= right) { | while(left <= right) { | ||
| + | mid = (int)(((double)target - arr[left]) / (arr[right] - arr[left]) * (right - left) + left); | ||
| - | middle = (left + right) / 2; | + | if(arr[mid] < target) |
| - | + | left = mid + 1; | |
| - | if(target | + | else if (arr[mid] > target) |
| - | right = middle | + | right = mid - 1; |
| - | } | + | |
| else { | else { | ||
| - | left = middle + 1; | + | System.out.println(count); |
| + | return mid; | ||
| } | } | ||
| - | + | count++; | |
| - | if(list.get(middle) <= target && middle < list.size() - 1) { | + | |
| - | if(target < list.get(middle | + | |
| - | return list.get(list.size() > middle | + | |
| - | } | + | |
| - | } | + | |
| } | } | ||
| - | return -1; | + | return |
| + | } | ||
| + | </ | ||
| + | |||
| + | |||
| + | * 재귀적 구현 | ||
| + | <sxh java ; highlight: | ||
| + | public static int interpolationSearchRecursive(int[] arr, int target, int left, int right) { | ||
| + | if(arr[left] > target || arr[right] < target) // 값의 범위를 넘어서는 경우 있음. | ||
| + | return Integer.MIN_VALUE; | ||
| + | |||
| + | int mid = (int)(((double)target - arr[left]) / (arr[right] - arr[left]) * (right - left) + left); | ||
| + | |||
| + | if(arr[mid] < target) | ||
| + | return interpolationSearchRecursive(arr, | ||
| + | else if (arr[mid] > target) | ||
| + | return interpolationSearchRecursive(arr, | ||
| + | else | ||
| + | return mid; | ||
| + | } | ||
| + | </ | ||
| + | |||
| + | |||
| + | * A ＜ X ≤ B 조건을 검색. (반환값이 index+1 이므로) | ||
| + | |||
| + | |||
| + | 첫번째 값을 찾지 못하는 Bug 있음. | ||
| + | |||
| + | |||
| + | <sxh java> | ||
| + | // 보간탐색을 이용한 근사값 찾기 | ||
| + | public static int interpolationSearch(char[] arr, int left, int right, int target) { | ||
| + | int mid = 0; | ||
| + | |||
| + | while(left <= right) { | ||
| + | mid = (int)(((double)target - arr[left]) / (arr[right] - arr[left]) * (right - left) + left); | ||
| + | |||
| + | // index가 left보다 크고, right보다 작을 때 | ||
| + | if(mid > left && mid < right) { | ||
| + | if(arr[mid - 1] < target && target <= arr[mid]) { | ||
| + | return mid + 1; | ||
| + | } | ||
| + | } | ||
| + | else if (mid == left) { | ||
| + | return left + 1; | ||
| + | } | ||
| + | else | ||
| + | return Integer.MIN_VALUE; | ||
| + | |||
| + | |||
| + | if(arr[mid] < target) | ||
| + | left = mid + 1; | ||
| + | else if (arr[mid] > target) | ||
| + | right = mid - 1; | ||
| + | } | ||
| + | |||
| + | return Integer.MIN_VALUE; | ||
| } | } | ||
| </ | </ | ||