Jawa / Говнокод #19523 Ссылка на оригинал

0

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
  45. 45
  46. 46
  47. 47
  48. 48
  49. 49
  50. 50
  51. 51
  52. 52
  53. 53
  54. 54
  55. 55
  56. 56
  57. 57
  58. 58
  59. 59
  60. 60
  61. 61
  62. 62
  63. 63
  64. 64
  65. 65
  66. 66
  67. 67
  68. 68
  69. 69
  70. 70
  71. 71
public class BinarySearch {
    // for all i in [1..n): a[i - 1] >= a[i]
    public static int iterative_binary_search(int[] a, int x) {
        int l = -1, r = a.length;

        // (l == -1 || a[l] > x) && (r == a.length || a[r] <= x)
        while (l < r - 1) {
            assert (l < 0 || a[l] > x) && (r >= a.length || a[r] <= x);

            int mid = l + (r - l) / 2;
            if (a[mid] <= x) {
                r = mid;
            }
            else {
                l = mid;
            }
        }

        return r;
    }
    // if (exists i: a[i] <= x) then
    //     result = min i: a[i] <= x
    // else
    //     result = a.length


    // for all i in [1..n): a[i - 1] >= a[i]
    public static int recursive_binary_search(int[] a, int x) {
        return recursive_binary_search(a, x, -1, a.length);
    }
    // if (exists i: a[i] <= x) then
    //     result = min i: a[i] <= x
    // else
    //     result = a.length


    // for all i in [1..n): a[i - 1] >= a[i]
    // -1 <= l < r <= a.length
    // (l == -1 || a[l] > x) && (r == a.length || a[r] <= x)
    public static int recursive_binary_search(int[] a, int x, int l, int r) {
        if (l >= r - 1) {
            return r;
        }

        int mid = l + (r - l) / 2;
        if (a[mid] <= x) {
            r = mid;
        }
        else {
            l = mid;
        }

        return recursive_binary_search(a, x, l, r);
    }
    // if (exists i in ([l, r] intersect [0, a.length)): a[i] <= x) then
    //     result = min i: in ([l, r] intersect [0, a.length)): a[i] <= x
    // else
    //     result = r


    public static void main(String[] args) {
        int a[] = new int[args.length - 1];
        for (int i = 1; i < args.length; ++i) {
            a[i - 1] = Integer.parseInt(args[i]);
        }

        int x = Integer.parseInt(args[0]);

        System.out.println(iterative_binary_search(a, x));
    }
}

Запостил: artemohanjanyan artemohanjanyan, (Updated )

Комментарии (17) RSS

    • ava bormand # Ссылка на оригинал 0 ⇈

      Там ещё кучу альтернативного кода раскомментить можно...
      Ответить

    • ava roman-kashitsyn # Ссылка на оригинал 0 ⇈

      Это не алтернатива. Это, похоже, предусловия, инварианты, и постусловия выписаны. Типа design by contract, вот это всё.
      Поскольку это на 146% лаба, ничего плохого в этом не вижу. Скорее, наоборот.

      И вообще, может, этот код скомпиллирован в жабу из декларативного языка более высокого уровня, и компилятор вставил куски оригинальных исходников для удобства чтения кофейного ассемблера
      Ответить

      • ava artemohanjanyan # Ссылка на оригинал 0 ⇈

        Это просто руками написанный код на джаве, и руками написанные контракты.
        И вообще я вместо заблоченного пастбина сюда захожу.
        Ответить

Добавить комментарий

Семь раз отмерь — один отрежь, guest!

    А не использовать ли нам bbcode?

    ↑
    8
    ↓