This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| algorithm:binary_search [2016/06/07 15:12] – ledyx | algorithm:binary_search [2021/02/07 03:15] (current) – external edit 127.0.0.1 | ||
|---|---|---|---|
| Line 41: | Line 41: | ||
| else | else | ||
| return mid; | return mid; | ||
| - | } | ||
| - | </ | ||
| - | |||
| - | |||
| - | * A ＜ X ≤ B 조건을 검색. (반환값이 index+1 이므로) | ||
| - | <sxh java> | ||
| - | public static int binarySearch(ArrayList< | ||
| - | |||
| - | int left = 0; | ||
| - | int right = list.size() - 1; | ||
| - | int middle = 0; | ||
| - | |||
| - | while(left <= right) { | ||
| - | |||
| - | middle = (left + right) / 2; | ||
| - | |||
| - | if(target < list.get(middle)) { | ||
| - | right = middle - 1; | ||
| - | } | ||
| - | else { | ||
| - | left = middle + 1; | ||
| - | } | ||
| - | |||
| - | |||
| - | if(list.get(middle) <= target && middle < list.size() - 1) { | ||
| - | if(target < list.get(middle + 1)) { | ||
| - | return list.get(list.size() > middle + 1 ? middle + 1 : list.size() - 1); | ||
| - | } | ||
| - | } | ||
| - | } | ||
| - | |||
| - | return -1; | ||
| } | } | ||
| </ | </ | ||
| Line 123: | Line 91: | ||
| else | else | ||
| return mid; | 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; | ||
| } | } | ||
| </ | </ | ||