rotated_array_search.dart

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);
}