This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| algorithm:binary_search [2016/06/19 09:56] – [Interpolation Search (보간 탐색)] ledyx | algorithm:binary_search [2021/02/07 03:15] (current) – external edit 127.0.0.1 | ||
|---|---|---|---|
| Line 96: | Line 96: | ||
| * A ＜ X ≤ B 조건을 검색. (반환값이 index+1 이므로) | * A ＜ X ≤ B 조건을 검색. (반환값이 index+1 이므로) | ||
| + | |||
| + | |||
| + | 첫번째 값을 찾지 못하는 Bug 있음. | ||
| + | |||
| + | |||
| <sxh java> | <sxh java> | ||
| // 보간탐색을 이용한 근사값 찾기 | // 보간탐색을 이용한 근사값 찾기 | ||
| Line 103: | Line 108: | ||
| while(left <= right) { | while(left <= right) { | ||
| mid = (int)(((double)target - arr[left]) / (arr[right] - arr[left]) * (right - left) + left); | mid = (int)(((double)target - arr[left]) / (arr[right] - arr[left]) * (right - left) + left); | ||
| - | + | ||
| - | System.out.println(" | + | // index가 |
| - | + | if(mid > left && mid < right) { | |
| - | if(arr[mid] < target) | + | |
| - | left = mid + 1; | + | |
| - | else if (arr[mid] > target) | + | |
| - | right = mid - 1; | + | |
| - | | + | |
| - | // index가 | + | |
| - | if(mid >= 1 && mid != arr.length - 1) { | + | |
| if(arr[mid - 1] < target && target <= arr[mid]) { | if(arr[mid - 1] < target && target <= arr[mid]) { | ||
| return mid + 1; | return mid + 1; | ||
| } | } | ||
| } | } | ||
| - | else if (mid == 0) { | + | else if (mid == left) { |
| - | return 1; | + | return |
| } | } | ||
| else | else | ||
| return Integer.MIN_VALUE; | return Integer.MIN_VALUE; | ||
| + | |||
| | | ||
| + | if(arr[mid] < target) | ||
| + | left = mid + 1; | ||
| + | else if (arr[mid] > target) | ||
| + | right = mid - 1; | ||
| } | } | ||