Created
March 21, 2023 11:35
-
-
Save vlastachu/f4835edaec8309a839cc7b838209a391 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import 'dart:math'; | |
import 'package:cli/cli.dart' as cli; | |
abstract class AbstactBinarySearch { | |
final List<int> nums; | |
final int target; | |
int start = 0; | |
int end; | |
AbstactBinarySearch(this.nums, this.target): end = nums.length - 1; | |
bool foundCondition(int guessIndex); | |
bool shouldMoveLeft(int guessIndex); | |
int getMiddle(int start, int end) { | |
return (start + end) ~/ 2; | |
} | |
int perform() { | |
while (start <= end) { | |
int middle = getMiddle(start, end); | |
if (foundCondition(middle)) { | |
return middle; | |
} | |
if (shouldMoveLeft(middle)) { | |
end = middle - 1; | |
} else { | |
start = middle + 1; | |
} | |
} | |
return -1; | |
} | |
} | |
class RawBinarySearch extends AbstactBinarySearch { | |
RawBinarySearch(super.nums, super.target); | |
@override | |
bool foundCondition(int guessIndex) { | |
return nums[guessIndex] == target; | |
} | |
@override | |
bool shouldMoveLeft(int guessIndex) { | |
return nums[guessIndex] > target; | |
} | |
} | |
class FindOffset extends AbstactBinarySearch { | |
FindOffset(super.nums, super.target); | |
@override | |
bool foundCondition(int guessIndex) { | |
if (nums.length == 1) { | |
return true; | |
} | |
final safePrevious = guessIndex == 0 ? nums.length - 1 : guessIndex - 1; | |
return nums[guessIndex] < nums[safePrevious]; | |
} | |
@override | |
bool shouldMoveLeft(int guessIndex) { | |
return nums[end] > nums[start] || nums[start] > nums[guessIndex]; | |
} | |
} | |
class FindNumInRotatedList extends AbstactBinarySearch { | |
final int offset; | |
FindNumInRotatedList(super.nums, super.target, this.offset); | |
int getIndexWithOffset(int index) { | |
return (index + offset) % nums.length; | |
} | |
@override | |
bool foundCondition(int guessIndex) { | |
return nums[getIndexWithOffset(guessIndex)] == target; | |
} | |
@override | |
bool shouldMoveLeft(int guessIndex) { | |
return nums[getIndexWithOffset(guessIndex)] > target; | |
} | |
@override | |
int perform() { | |
final result = super.perform(); | |
return result == -1 ? -1 : getIndexWithOffset(result); | |
} | |
} | |
class OnePassRotatedSearch extends AbstactBinarySearch { | |
OnePassRotatedSearch(super.nums, super.target); | |
@override | |
bool foundCondition(int guessIndex) { | |
return nums[guessIndex] == target; | |
} | |
@override | |
bool shouldMoveLeft(int guessIndex) { | |
final guess = nums[guessIndex], s = nums[start], e = nums[end]; | |
return guess >= s | |
? guess >= target && s <= target | |
: !(guess <= target && e >= target); | |
} | |
} | |
void expect(int got, int expected) { | |
print( | |
'got: $got; expected: $expected; ${got == expected ? 'SUCCESS' : 'FAIL'}'); | |
} | |
int rotatedArraySearch(List<int> nums, int target) { | |
final offset = FindOffset(nums, target).perform(); | |
return FindNumInRotatedList(nums, target, offset).perform(); | |
} | |
void main(List<String> arguments) { | |
const sample1 = [0, 1, 2, 3, 4, 5, 6, 7, 8]; | |
print('=== RAW TESTS'); | |
for (final sampleTarget in sample1) { | |
final r = RawBinarySearch(sample1, sampleTarget).perform(); | |
expect(r, sampleTarget); | |
} | |
print('=== OFFSET TESTS'); | |
expect(FindOffset([4, 5, 6, 7, 0, 1, 2], 0).perform(), 4); | |
expect(FindOffset([4, 5, 6, 0, 1, 2], 0).perform(), 3); | |
expect(FindOffset([1, 2, 3], 3).perform(), 0); | |
print('=== FULL TESTS'); | |
expect(rotatedArraySearch([4, 5, 6, 7, 0, 1, 2], 0), 4); | |
expect(rotatedArraySearch([1], 0), -1); | |
expect(rotatedArraySearch([4, 5, 6, 7, 0, 1, 2], 3), -1); | |
expect(rotatedArraySearch([1], 1), 0); | |
expect(rotatedArraySearch([1, 2, 3], 3), 2); | |
print('=== ONE PASS'); | |
onePass(List<int> nums, int target) => OnePassRotatedSearch(nums, target).perform(); | |
expect(onePass([4,5,6,7,8,1,2,3], 8), 4); | |
expect(onePass([5, 1, 3], 5), 0); | |
expect(onePass([4, 5, 6, 7, 0, 1, 2], 0), 4); | |
expect(onePass([1], 0), -1); | |
expect(onePass([4, 5, 6, 7, 0, 1, 2], 3), -1); | |
expect(onePass([1], 1), 0); | |
expect(onePass([1, 2, 3], 3), 2); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment