C DSALesson 58Free preview

C Searching

This lesson is part of C · All levels

Summary

The search is aimed at finding the position of a value within a data set. Linear search checks elements one by one and can be used on unordered data, whereas binary search divides the search space into two so much faster, but requires data to be sorted. Understanding the prerequisites of each algorithm prevents wrong outcomes while speeding up the program.

Key points

Linear search runs O(n) and is suitable for small or unsearched data.
Binary search is running but requires data to be sorted.
How binary search works: compare the mean, then throw out half the impossible search space.
Returns the index when found and the special marker like -1 when none exists.
For text search, matches are checked per character until they reach the terminator.

Full lesson

Code examples and quizzes

Full lessons, code examples, and quizzes are available to subscribers. 5 questions.