What History Gives Us to Work With
Many pre-modern civilizations had police forces of various sorts. Most were just military personnel, bounty hunters, or bodyguards of public officials, but some larger civilizations had proper police forces. The big difference between now and then was not the existence of people to enforce the laws but the differences in training, accessibility, technology, and structure.
Training: Modern cops have access to specialized training based on decades of research into human psychology that helps them de-escalate volatile situations and effectively interrogate people for the truth. Without this training, police forces are much more likely to resort to violence as a first response; so, when an untrained cop comes across a domestic dispute, it's more likely to end in floggings for everyone than a peaceful resolution.
Accessibility: The invention of the telephone has made police much more able to respond to issues in real time. If there is a crime being committed now, you have a good chance of being able to contact an officer within a relatively short amount of time, but in most ancient cities, the best you can do is walk to the nearest magistrate building and report the crime well after it's happened. This lack of accessibility meant that common citizens were much more expected to carry arms for self defense and perform citizen's arrests as necessary.
Technology: Modern forensics is an unfathomably huge factor in what makes modern legal systems different. In pre-modern times, there was literally no way to prove a crime 99% of the time; so, there is no real basis for the role of a detective or evidence based trial in such a setting. Instead most criminal disputes were resolved by who was "more trustworthy" which typically translated to who has the higher social status. This also made the prosecution of nobility nearly impossible.
Structure: Modern police forces are designed to follow the same set of rules they enforce. They are separate from the judicial system whereas most medieval police like forces were retainers of the lords who also wrote the laws and judged all cases. This separation helps keep modern police from accumulating to much political power and losing track of thier function of protection and serving.
How to Mix and Match
Training: The most sophisticated and specialized pre-modern police force were probably the Roman Vigiles. Literally translates to "watch men". The Vigiles were full time professionals hired to patrol the streets, enforce the laws, prevent fires, and arrest criminals. In other words they were the police and fire department all wrapped into one. Because they were non-military professionals, Rome could devote enough time to properly train thier police forces to be "police" and not "city guards". This distinction is important when training police because the later is trained on how to deal with enemies whereas police are trained how to deal with citizens.
Accessibility: Again, the Roman Vigiles are going to be your best blueprint for this. While you can not achieve the same level of accessibility as modern cops without phones, the fact that they partrolled the city streets is a HUGE improvement over most other pre-modern police entities. This means they had eyes on places where crime was most likely (shops, ports, major road, etc.) and there was always a chance that no matter where you were in the city that if you did something illegal that a Vigil might walk by and catch you doing it. So, not as accessible as modern cops, but certainly comparable to the police forces of the 1800s. You could also give your cops pipe whistles (invented in the 1200s) so they could coordinate over large distances similar to how early British police did.
Technology: This is going to be your hardest hurdle because your setting by definition does not have modern tech. This means you have no forensics evidence with which to create reasonable evidence of most crimes. This means you need a system that decides what reasonable evidence is in lue of proof. In a modern courtroom, evidence is evaluated by Subject Matter Experts who are professionals who specialize in the analysis of certain kinds of evidence. Judges and juries turn to these people's rhetoric to really make the case of guilt or innocence more so than the evidence itself which is often far to technical or abstract to actually be evaluated by non experts.
This means that your courts will need to employ the best experts at getting the truth you have such as fortune tellers or torturers...
Or, if you want a more fair system and don't mind going into non-historical systems, you could add a special class of fictional investigator to your society who are just people renowned for thier ability to use logic and observation to find the truth. Think Sherlock Holmes, Shawn Spencer, or Dr. Lightman, but instead of this being a single exceptional person in your story, have an entire bureau of such people drawn from society with these special talents who are then trained to push those talents to thier absolute human limits. In reality, veteran cops are usually right about who is guilty even when they can not prove it; so, at its core, this is a system that relies on the fine tuned intuition of the best of the best cops to help judges make thier final decisions.
Structure: Marrying historical feudalism and a modern law enforcement system is mutually exclusive. Feudal law gave local lords unlimited executive, legislative, & judicial power within thier own fiefdom which means that "law" is not a justice system but a set of guidelines designed to set expectations, but those expectations could simply be ignored when it is convenient to those in power.
To get around this without totally abolishing feudalism, you need to separate your lords into judges, executives, and legislators. For example, it could be that only the King has the right to pass laws, only provincial lords have the right to command and organize the police forces (like a county Sheriff), and only local lords like knights would have the right to preside over legal cases.