二分探索やlower_boundなどを使わない解法を紹介します。

$\left( A_i,1 \right),\left( B_i,2 \right)$ の $N+M$ 個のpairからなる配列 $C$ を用意し、これを $1$ 番目の値でsortします。タイブレークは $2$ 番目の値に従ってsortします。
次に、隣り合う $C$ のpairについて、 $2$ 番目の値が異なるならば $1$ 番目の値の差を計算し、それらの最小値を出力するという方針を考えます。

実は、この方針で正解することができます。この解法の正当性を考えます。初めに、 $A_i$ は全て異なるとして構いません。 $B_i$ についても同様です。(これは簡潔に正当性を確認するためで、実装ではこれが成り立ってなくても問題ありません)
まず、 $A_i=B_j \left( = V \right)$ となるような $\left(i,j \right)$ が存在するとします。このとき答えは明らかに $0$ です。また、 $C$ には $\left(V,1 \right),\left(V,2 \right)$ が存在しており、これらは上のsortの方法だと隣り合うので最初の方針だと $0$ を出力します。よってこの場合は正解できます。
そうでない場合、ある $i,j$ について $|A_i-B_j|$ が最小になるとします。対照性より $A_i < B_j$ として構いません。ここで、 $A_i < A_k < B_j$ もしくは $A_i < B_k < B_j$ となるような $k$ が存在するとします。このとき、前者なら $|A_k - B_j| < |A_i-B_j|$ となり後者なら $|A_i - B_k| < |A_i-B_j|$ となるのでこのような $i,j$ は最適ではありません。
同様に考えることで、最適な値を取る $A_i,B_j$ について $A_i$ と $B_j$ の間となる値は $A,B$ の中に存在しないことが示せます。よって、 $C$ の隣接するpairのみに着目することで十分であり、最初の方針に正当性が成り立ちます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n,m;
  cin>>n>>m;

  vector<pair<int,int>> v;
  for(int i=0;i<n;i++){
    int a;
    cin>>a;
    v.emplace_back(a,1);
  }
  for(int i=0;i<m;i++){
    int b;
    cin>>b;
    v.emplace_back(b,2);
  }
 
  sort(v.begin(),v.end());
 
  int ans=2e9;
  for(int i=0;i<n+m-1;i++){
    if(v[i].second!=v[i+1].second){
      ans=min(ans,v[i+1].first-v[i].first);
    }
  }
  cout<<ans<<endl;
}