이분탐색 & Upper Bound & Lower Bound

이분탐색 & Upper Bound & Lower Bound

이분탐색

static int binarySearch(int[] arr, int key) { int start = 0; int end = arr.length -1; while(start <= end) { int mid = (start+end)/2; if(key < arr[mid]) { end = mid-1; } else if(key > arr[mid]) { start = mid+1; } else { // key == mid return mid; // 존재하면 인덱스 출력 } } return -1; // 존재하지 않으면 음수 출력 }

LowerBound & UpperBound 이해

https://st-lab.tistory.com/267

https://blog.naver.com/bestmaker0290/220820005454

L owerBound

static int lowerBound(int[] arr, int key) { int lo = 0; int hi = arr.length; // lo가 hi랑 같아질 때까지 반복 while(lo < hi) { int mid = (lo + hi) / 2; // 중간위치를 구한다. /* * key 값이 중간 위치의 값보다 작거나 같을 경우 * * 중복 원소에 대해 왼쪽으로 탐색하도록 상계를 내린다. */ if(key <= arr[mid]) { hi = mid; } else { lo = mid + 1; } } return lo; }

UpperBound

static int upperBound(int[] arr, int key) { int lo = 0; int hi = arr.length; // lo가 hi랑 같아질 때 까지 반복 while(lo < hi) { int mid = (lo + hi) / 2; // 중간위치를 구한다. // key값이 중간 위치의 값보다 작을 경우 if(key < arr[mid]) { hi = mid; } // 중복원소의 경우 else에서 처리된다. else { lo = mid+1; } } return lo; }

from http://yeonobly.tistory.com/65 by ccl(A) rewrite - 2021-11-18 18:28:01