Add searching algorithms for linear data structures

[EmperorArthurIX]

Description of the problem

The codebase is very extensive and well-designed; however, it does not seem to include searching algorithms for linear data structures as far as I could observe. I believe addition of searching algorithms would be a good improvement to the project. Certain algorithms I have thought can be included are:

• Linear Search(array, number)

• Binary Search(array, number, unsorted_input=False)

• Jump Search(array, number, unsorted_input=False)

The above mentioned declarations are suggested, where the parameter unsorted_input can be used to explicitly learn from the user whether or not the input array is sorted beforehand. If True, we must first sort the array within the search function, then search.

Comments

With certain modifications, we may even allow to return the sorted array along with search result, but I have no idea on how that will be done at the moment.

PS: I am currently working on the Radix Sort issue that is already open, and after that reaches a satisfactory stage, I wish to go on with this one. Discussions and suggestions are welcome.

[HarsheetKakar]

With binary search and jump search in mind we can also have a SortedOneDimentionalArray as data structure which would take OneDimentionalArray as input and would dynamically choose the sorting algorithm based on how far the array is already sorted which would come from its Hamming Distance (wheather it would be insertionSort which works best for nearly sorted arrays and quickSort if the array is not sorted).

[czgdp1807]

Interesting idea. I think the idea of SortedOneDimensionalArray should be discusses in a separate issue. Is there any prior work (like Wikipedia article, papers, or lecture notes available online) which can provide clarity and examples?

[HarsheetKakar]

I have moved the conversation to Gitter once we reach a consensus I will create a separate issue.

[czgdp1807]

Gitter

It's inactive. Folks use Discord these days a lot. Github issue would be the best place to discuss as it is accessible by anyone in the open source community.

[czgdp1807]

And may be we should provide a function that should take an array as input and suggest one of the pydatastructs APIs as output. The time complexity should be O(n) because anything more won't be worth it. The constant in O(n) should also be very small (we can benchmark for that).

[czgdp1807]

The above mentioned declarations are suggested, where the parameter unsorted_input can be used to explicitly learn from the user whether or not the input array is sorted beforehand. If True, we must first sort the array within the search function, then search.

I think that if a searching algorithm require input array to be sorted then it should assume that. Otherwise we won't be able to guarantee lower time complexities of algorithms like binary search, exponential search. The overhead of sorting an array is non-trivial, in-fact even checking whether an array is sorted or not will take o(n) time which is large as compared to O(logn) promised by binary search. So, let's keep things simple and encapsulated for now. I would suggest something like this, search(input_array, algorithm) where algorithm would be a string (non-optional argument), binary_search, linear_search, jump_search, exponential_search, etc.

[EmperorArthurIX]

The above mentioned declarations are suggested, where the parameter unsorted_input can be used to explicitly learn from the user whether or not the input array is sorted beforehand. If True, we must first sort the array within the search function, then search.

I think that if a searching algorithm require input array to be sorted then it should assume that. Otherwise we won't be able to guarantee lower time complexities of algorithms like binary search, exponential search. The overhead of sorting an array is non-trivial, in-fact even checking whether an array is sorted or not will take o(n) time which is large as compared to O(logn) promised by binary search. So, let's keep things simple and encapsulated for now. I would suggest something like this, search(input_array, algorithm) where algorithm would be a string (non-optional argument), binary_search, linear_search, jump_search, exponential_search, etc.

Noted, will think of solutions from that perspective while planning and coding.

[czgdp1807]

The input should not necessarily be an array. A function should work too. An array is conceptually also a function (of indices). See this https://en.wikipedia.org/wiki/Ternary_search for example. Allowing inputs as function would make API more practical.

[r-avenous]

Shall I work on this one?

[czgdp1807]

Sure go ahead.