참고: java binarySearch예제
Comparator<Person> ageComparator = Comparator.comparingInt(Person::getAge);
int index = Arrays.binarySearch(people, new Person("Bob", 30), ageComparator);
(찾으면 >=0 못찾으면 -index-1 리턴)
아래는 없을땐 -1 리턴하는 java 코드들입니다.
<sort된 array내에서 exact매칭을 위한 BinSearch >
public int binSearch ( int A[], int target ){
int low = 0;
int high = A.length -1;
int mid = 0;
while (low <= high ){
mid = (low+high)/2;
if ( A[mid] < target) low = mid+1;
else if ( A[mid] > target ) high = mid -1;
else
return mid;
}
return -1;
}
<sort + rotate된 array내에서 exact매칭을 위한 BinSearch >
예) [4,5,6,7,8, 0,1,2,3] 에서 target이 2인경우 ==> 정 답: 7
public int search(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
int mid = 0;
while (low <= high) {
mid = (low + high) /2;
if (nums[mid] == target) return mid;
//left half sorted
else if (nums[low] <= nums[mid] ) {
//target이 left 존재 (mid제외)
if (nums[low] <= target && nums[mid] > target) {
high = mid - 1;
}
else low = mid + 1;
}
//right half sorted
else {
//target이 right에 존재 (mid 제외)
if (nums[mid] < target && nums[high] >= target )
low = mid + 1;
else
high = mid - 1;
}
}
return -1;
}
<LE를 위한 BinSearch > : LE - lessthan or Equal을 만족하는 최대 index 리턴.
// A:{1,2,5, 9, 10}, target:7 => index:2 return이 목표.
public int binSearchLE ( int A[], int target ){
int low = 0;
int high = A.length -1;
int mid = 0;
while (low <= high) {
mid = (low+high)/2;
if ( A[mid] < target) low = mid+1;
else if ( A[mid] > target ) high = mid -1;
else
return mid;
}
if ( mid>0 ) {
if (A[mid] < target ) //LE CHeck
return mid;
if (A[mid] > target && A[mid-1] < target )
return mid-1;
}
if (mid==0){ //mid가 0일경우는 어떡하나?
if (A[0] < target) return 0;
}
return -1;
}
======> 마지막 2개의 if를 간단히 3줄로도 줄일 수 있음.
if (arr[mid] < target) return mid;
else if (mid > 0 && arr[mid] > target && arr[mid-1] < target)
return mid -1;
//// low,high trace ///////////////////////
0,4 -> mid:2 if
3,4 -> mid:3 else_if
3,3 -> (mid:3) else_if
=> low,high가 마지막 loop이므로 이때 one more check가 필요.
return -1;
<GE를 위한 BinSearch > : GE - grea than or Equal을 만족하는 최소 index 리턴.
// A:{1,2,5, 9, 10}, target:7 => index:3 return이 목표.
public int binSearchGE ( int A[], int target ){
int low = 0;
int high = A.length -1;
int mid = 0;
while (low <= high) {
mid = (low+high)/2;
if ( A[mid] < target) low = mid+1;
else if ( A[mid] > target ) high = mid -1;
else
return mid;
}
if ( mid < A.length-1 ) {
if ( A[mid] < target && A[mid+1] > target )
return mid+1;
if (A[mid] > target ) //GE CHeck
return mid;
}
if (mid==A.length-1){ //?
if (A[mid] > target)
return (A.length-1);
}
return -1;
}
//// low,high trace ///////////////////////
0,4 -> mid:2 if
3,4 -> mid:3 else_if
3,3 -> (mid:3) else_if
=> low,high가 마지막 loop이므로 이때 one more check가 필요.
return -1;
