Both approaches are right, either overriding a method, or subclassing.
By “right”, I mean, you can craft a program that works, with either approach.

Yet I suggest to take the a class definition for each search, it’s more flexible.

You can add properties, and replace the “Search” method, and add more search ways, just by adding classes. It seems a little complicated first, but, in real world, makes your application easier to extend.

Also, split each search method, in an specific class.

public abstract class SingleSearchClass : Object
{
  public ReturnDataType Search(Object SomeParameters){};
}

public /* concrete */ class QuickSearchClass : SearchAbstractClass
{
  public ReturnDataType Search(Object SomeParameters){};
}

public /* concrete */class HeuristicsSearchClass : SearchAbstractClass
{
  public ReturnDataType Search(Object SomeParameters){};
}

public /* concrete */ class RandomSearchClass : SearchAbstractClass
{
  public ReturnDataType Search(Object SomeParameters){};
}

And declare a wrapper / adapter, that let the user choose the different available search methods:

public enum SearchMethodEnum
{
  NoSearch,
  QuickSearch,
  HeuristicsSearch,
  RandomSearch,
}   

public /* concrete */ class SearchClientClass : Object
{
  public /* property*/ SearchMethodEnum SearchMethod
    { get; set; }

  public /* property*/ Object Params
    { get; set; }

  public ReturnDataType Execute()
  {
    ReturnDataType Result = null;          

      if (this.SearchMethod != SearchMethodEnum.NoSearch)
      {
        SingleSearchClass Search = null;

        switch (this.SearchMethod)
        {
          case SearchMethodEnum.QuickSearch:
            Search = new SearchClientClass();
          break;

          case SearchMethodEnum.HeuristicsSearch:
            Search = new HeuristicsSearchClass ();
          break;

          case SearchMethodEnum.RandomSearch:
            Search = new RandomSearchClass ();
          break;
        } // switch

        Result = Search.Search(this.Params);
      } // if

    return Result;
  }
} // class SearchClientClass

And, a generic example (pseudocode):

public /* concrete */ class SearchExampleClass
{   
  public static void main(string[] args)
  {
    SearchClientClass Client = new SearchClientClass();

    Client.Params = "John Doe";
    Client.SearchMethod = SearchMethodEnum.QuickSearch;

    ReturnDataType Result = Client.Execute();

    Client = null;
  }

}

[UPDATE] Extend description.

Just my 2 cents.

Your semantics are all off based on the intentions.

public ReturnDataType findBasedOnStaticQuery(){};
public ReturnDataType findByPredeterminedFields(Fields...){};
public ReturnDataType findBySomethingElse(){};

The point of naming methods is to convey their intent, not their implementation.

getXXX usually means to retrieve and private instance value, get is not a good prefix when you are really doing searches. findXXX is more semantically correct.

in both cases you have names like frobnicateTypeA and frobnicateTypeB. This is a strong indications that you should be passing instances of these types as parameters instead.

In this specific case, you are trying to design a system to perform queries. Let’s collect a few general parameters:

• users can use different methods to run a query, e.g. a form-based interface or natural language processing.
• users can search by different properties, e.g. by parcel owner or by parcel address.

I find it important to note that hardcoding this in method names is not desirable, as it hinders extensibility:

• You may want to add a different query method. E.g. you might have to add a speech-based query method. Do you want to add a GetResultsMethodSpeech method to each class that happens to touch query methods?

  Luckily, this can be avoided.

• You may want to allow queries for additional properties, such as parcel receiver or parcel weight or estimated time of arrival. Do you really want to have to add another method to each class that happens to touch these properties?

  Sadly, this can’t be avoided.

In short, both of your suggested architectures do not scale.

The key to the solution is that all query methods are just different expressions of the same content – with each query method there is an equivalent way to express the same query. Therefore, there will be only one class representing the query, but different functions assembling this query from the user input. E.g. we could have a QueryFactory that emits Querys. You would then pass that query on to some database wrapper.

class Query { ... }

class QueryFactory {
    public Query FromForm(FormData);
    public Query FromNLP(String);
    public Query FromAudio(AudioRecording);
}

// in the controller, different handlers would then invoke
// the correct method in the factory, and pass the query to the DB
QueryFactory makeQuery = ...;

database.Execute(makeQuery.FromForm(formInput));

// or in a different handler:
database.Execute(makeQuery.FromAudio(audioInput));

To add an additional query method, you only have to add the actual parsing logic for that kind of query method, and have to add the code for that specific user interface. You do not have to add any code in the classes that actually execute that query.

I do not know, if I am getting you right, but as far as I understand, you have the following scenario:

1) You have different kinds of querying:

• search by owner
• search by destination address
  …

2) Each of which has e.g different sources or whatever

So the best way to solve this would be via strategy.
Defining the allowed queries in an interface (supposing you were writing C#):

interface IQueryMechanism
{
   Result SearchByOwner(string owner);
   ...
}

Then defining a Service which takes care of the ingoing calls.

public class ParcelService 
{
    IQueryMechanism mechanism;

    public void setQueryMechanism(IQueryMechanism mechanism) { this.mechanism=mechanism; }
    public SearchByOwner(string owner) { return mechanism.SearchByOwner(string owner);} 
}

When you instantiate the ParcelService you could inject the appropriate mechanism via setter injection (for readability reasons I left guarding clauses out). So everytime a request comes in, the repository delegates this request to the underlying mechanism.

And your mechanism-class looks like

public class OnlineSearch : IQueryMechanism  
{
    public SearchByOwner(string owner) { /* business logic here */} 
    ...
}

So you instantiate one Service and swap at runtime, the QueryMechanism.

Adapter & repository pattern

my examples are written in php, because it is more verbose.

The type problem

As far as I can make out, your ‘types’ are in fact DataObjects (or models, or entitites or what ever you want to call them). Each type extends thid basic DataOBject class:

class TypeA extends|implements DataObject {}
class TypeB extends DataObject {}

These data objects are representation of your data. They give you a nice set of methods to interact with the data. e.G. getGoo() and setBar('ook')

We also need a kind of interface to retrieve, create (CRUD stuff) the dataobjects. Thats where the repository comes in:

class TypeARepository extends AbstractRepository implements Repository {}

with

interface Repository
{
    public function findAll();

    public function findById($id);

    public function where($key, $operator, $value);
}

Now we have a nice interface to search our different types. Our controller doesn’t even care what type he is searching. As far he knows it’s just data returned from a repository:

class MyController
{
    private $repository;

    public function __construct(Repository $repository)
    {
        $this->repository = $repository;
    }
    public function doStuff()
    {
        $data = $this->repository->where('foo','=','bar');
        pass_to_View_magic($data);
    }
}

And we isntantiate that controller:

//the controller doesn’t car about what you pass in. as long as it is a Repository he can query.
$controller = new MyController(new TypeARepository());
$controller->doStuff();

But what about my different methods?

Your 3 different methods actually do the exact same thing. They search. The only thing they do is take in some kind of input and then pass it to the search function in the correct way. This is the adapter pattern. (google it). You can use the adapter pattern in functions of the Controller or as completly different classes:

class MyController
{
    private $repository;

    public function __construct(Repository $repository)
    {
        $this->repository = $repository;
    }
    public function doStuff()
    {
        $data = $this->repository->where('foo','=','bar');
        pass_to_View_magic($data);
    }
    public function doSuffDifferently($data)
    {
        $data = $this->repository->where($data[0],$data[1],$data[2]);
    }
}

Now doStuffand doStuffDifferently act as small adapters of you Repository interface.

Hoep this helped