Sidebar

Recent changes

Menu

Trace: • Radix Sort (기수 정렬) • Prototype Pattern • 이진 탐색 (Binary Search) • Programming Tips and Tricks • Template Method Pattern • Merge Sort (병합 정렬)
Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision		Previous revision
algorithm:binary_search [2016/06/07 14:14] – 만듦 ledyxalgorithm:binary_search [2021/02/07 03:15] (current) – external edit 127.0.0.1
Line 5: Line 5:
 {{tag>Algorithm, Search}} {{tag>Algorithm, Search}}
  
-  * 일반적인 구현+  * 일반적 구현
 <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<Integer> list, int target) {+
  
 +  * 일반적 구현
 +<sxh java ; highlight:[9]>
 + public static int interpolationSearch(int[] arr, int target) {
  int left = 0;  int left = 0;
- int right = list.size() - 1; + int right = arr.length - 1; 
- int middle = 0;+ 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 < list.get(middle)) { + else if (arr[mid] > target) 
- right = middle - 1; + 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 + 1)) { +
- return list.get(list.size() > middle + 1 ? middle + 1 : list.size() - 1); +
- } +
- }+
  }  }
   
- return -1;+ return Integer.MIN_VALUE; 
 + } 
 +</sxh> 
 + 
 + 
 +  * 재귀적 구현 
 +<sxh java ; highlight:[2,3,5]> 
 + 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, target, left + 1, right); 
 + else if (arr[mid] > target) 
 + return interpolationSearchRecursive(arr, target, left, right - 1); 
 + else 
 + return mid; 
 + } 
 +</sxh> 
 + 
 + 
 +  * 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;
  }  }
 </sxh> </sxh>
algorithm/binary_search.1465305257.txt.gz · Last modified: 2021/02/07 03:15 (external edit)