Greetings to everyone,
In this article, I will try to explain the most famous data search algorithms in Go language.
You can access the entire source code from the repo below. If you can improve performance or add new sorting techniques, I would be very happy.
https://github.com/MuratTunc/DataStructersGo/tree/main
Linear Search
Array: Sorted or non sequential
Algorithm: All array elements are checked sequentially, starting from the first element. The process ends when the searched number is found; otherwise, the entire array is scanned.
N-->Array size
Worst case-->2N+1 comparisons
The time complexity of linear search is O(n)
Sentinel Linear Search
Array: Sorted or non sequential
Algorithm: The number of comparisons are less in sentinel linear search than linear search. The difference from linear search is to reduce the number of comparisons.
N-->Array size
Worst case-->N+2 comparisons
The time complexity of Sentinel Linear Search O(n).
Jump Search
Array: Sorted
Algorithm: The aim is to reduce the number of comparisons and switch to the linear search algorithm by reducing the scanning area. The block size that determines the jump distance must be determined. The jumping process continues until a number greater than the searched element is found. When a number greater than the searched element is found, linear search is applied to the last piece in the background.
The complexity of Sentinel Jump Search is O(√N).(Worst Case)
Binary Search
Array: Sorted
Algorithm: The target number is compared with the middle element of the array, and if it is equal to the middle element, the operation is successful and the fastest result is obtained.
If it is not equal to the middle element, it is checked.
- If it is less than the middle element, a new search is started in the left half of the array.
- If it is larger than the middle element, the search starts in the right half of the array.
N-->Array size
The average time case complexity is O(logN)
Best Case Time Complexity of Binary Search Algorithm: O(1)
Interpolation Search
Array: Sorted
Algorithm: Dynamically adjusts the search range using a formula. Binary Search always goes to the middle element to check but Interpolation Search may go to different locations according to the value of the key being searched.
During this work, of course, I benefited from many open internet resources and tested all the codes. I will continue to improve as I have time.
Top comments (0)