Unable to find Median of 2 sorted Arrays using Racket

user_17397483 0
Viewed 58

I am trying to find the median of 2 sorted arrays using Binary Search in Racket. For reference kindly refer to approach 4 here But I can't seem to make the code work.

    (define (find-median x y n m)
    (define (loop l h realmid)
    (cond [(> l h) #f]
          [else (
                (let ()
                (define mid (/ (+ l h) 2))
                (define leftAsize mid)
                (define leftBsize (- realmid mid))
                (define leftA (if (> leftAsize 0) (vector-ref x (- leftAsize 1)) -inf.0)) 
                (define leftB (if (> leftBsize 0) (vector-ref y (- leftAsize 1)) -inf.0))
                (define rightA (if (< leftAsize n) (vector-ref x leftAsize) +inf.0))
                (define rightB (if (< leftBsize m) (vector-ref x leftAsize) +inf.0)))
                (cond 
                  [(and (<= leftA rightB) (<= leftB rightA)) (cond
                                                                [(= 0 (modulo (+ m n) 2)) ( / 2 (+ (max leftA leftB) (min rightA rightB)))]
                                                                [else (max leftA leftB)]
                                                                )]
                  [(> leftA rightB) (loop l (- mid 1) realmid)]
                  [else (loop (+ mid 1) h realmid)]))]))
    (define start 0)
    (define end n)
    (define realmid ( / (+ n m 1) 2))
    (loop start end realmid))
    
(define x (vector 1 2))
(define y (vector 3))
(define n (vector-length x))
(define m (vector-length y))
(cond [(> n m) (writeln (find-median y x m n))]
      [else (writeln (find-median x y n m))])

This is the error I am currently facing.

jdoodle.rkt:5:16: begin (possibly implicit): no expression after a sequence of internal definitions
  in: (begin (define mid (/ (+ l h) 2)) (define leftAsize mid) (define leftBsize (- realmid mid)) (define leftA (if (> leftAsize 0) (vector-ref x (- leftAsize 1)) -inf.0)) (define leftB (if (> leftBsize 0) (vector-ref y (- leftAsize 1)) -inf.0)) (define right...
  location...:
   jdoodle.rkt:5:16
   jdoodle.rkt:6:16
   jdoodle.rkt:7:16
   jdoodle.rkt:8:16
   jdoodle.rkt:9:16
   jdoodle.rkt:10:16
   jdoodle.rkt:11:16
   jdoodle.rkt:12:16

Thanks in advance for any help.

racket
1 Answers

Why not:

(define median (sorted-list)
  (let* ((len (length sorted-list))
         (mid (floor (/ len 2)))
         (mid-el (list-ref sorted-list mid)))
    (if (even? len)
        (/ (+ (list-ref sorted-list (- mid 1))
              mid-el)
           2)
        mid-el)))

(define merge-two-sorted-lists (sl1 sl2 (acc '()))
  (cond ((empty? sl1) (append (reverse acc) sl2))
        ((empty? sl2) (append (reverse acc) sl1))
        ((< (car sl1) (car sl2)) (merge-two-sorted-lists (cdr sl1) sl2
                                                         (cons (car sl1) acc)))
        (else (merge-two-worted-lists sl1 (cdr sl2) (cons (car sl2) acc)))))

(define median-of-two-sorted-lists (sl1 sl2)
  (median (merge-two-sorted-lists sl1 sl2)))

The median function is translated from Python:

def median(lst):
    n = len(lst)
    s = sorted(lst)
    return (s[n//2-1]/2.0+s[n//2]/2.0, s[n//2])[n % 2] if n else None
user_96900900
Related