How to Use Linear and Binary Search in C

TL;DR

Use linear search to inspect array elements sequentially, stopping when the target is found or the array ends. Use binary search only on a sorted array, where low, high, and mid indices repeatedly reduce the search space by half. Their stated running times are O(n) and O(log n), respectively, and both algorithms can be coded in C.

Transcript

In this course on Data Structures and Algorithms, we have seen a lot so far. In today's video we are going to talk about: linear search and binary search. What is Linear Search? And what is binary search? Today's video will tell you guys in a little more detail Although I gave a little idea to you guys in this video. The third or fourth video that ... Read More

Key Insights

• Linear search is an array traversal method that checks elements one by one until the target is found. If no element matches before traversal reaches the end, the search concludes that the target is not present in the array.
• Linear search works with both sorted and unsorted arrays because every candidate can be inspected independently of its position. The card-deck example demonstrates this process: cards are examined sequentially until the requested card, such as the six of hearts, appears.
• Binary search is a smarter search method that uses the ordering of data to reduce the candidate region. It begins with the full sorted array, examines a middle element, and then continues only in the portion that can still contain the target.
• A sorted array is the first condition for binary search. The book example shows why: page 238 can be located by using ordered page numbers, but the same narrowing method would fail if the pages from 1 to 1000 were stitched together randomly.
• Binary search tracks low, high, and mid indices throughout the process. In the demonstrated array, low begins at 0, high begins at 8, and the middle index is calculated from those boundaries as the greatest integer associated with their average.
• The comparison between the target and the middle value determines which search region remains relevant. If the middle value equals the target, the search ends. If it is smaller than the target, the algorithm continues toward the higher-index portion of the sorted array.
• Binary search reduces its search space repeatedly instead of traversing nearly the entire array. When searching for 200, middle values below 200 allow the lower portion to be excluded, after which a new middle index is calculated from the updated boundaries.
• Linear and binary search have stated running times of O(n) and O(log n), respectively. Linear search can still find an early element quickly, such as 2 or 8 in the example, while binary search becomes useful for exploiting order as an array grows.

Questions & Answers

Q: How does linear search work on an array?

Linear search visits array elements one by one and compares each value with the requested target. It stops as soon as a matching element is found. If traversal reaches the end of the array without a match, the algorithm reports that the target could not be found. Because this procedure checks values directly, it works on both sorted and unsorted arrays.

Q: Can linear search be used on an unsorted array?

Yes, linear search can be used on either a sorted or an unsorted array. Its procedure does not depend on the values being arranged in order. It simply examines the elements sequentially until it finds the requested value or reaches the end. The card-deck example illustrates this independence from ordering because each card can be checked one at a time.

Q: What condition is required for binary search?

Binary search requires the array to be sorted. Ordering lets the algorithm determine whether the target must lie below or above the current middle value, allowing the other portion to be excluded. The book analogy makes this requirement clear: ordered pages support narrowing toward page 238, while randomly stitched pages would prevent the same method from working.

Q: How does binary search reduce the search space?

Binary search starts with low and high boundaries covering the current array region, then calculates a middle index. It compares the middle value with the target and keeps only the portion where the target can still appear. Repeating this comparison and boundary update makes the search space progressively smaller until the value is found or no candidate region remains.

Q: What do low, high, and mid mean in binary search?

Low marks the lower boundary of the current search region, while high marks its upper boundary. Mid identifies a middle position calculated from those two indices. In the demonstrated example, low is 0 and high is 8, so mid becomes 4. These three tracked indices define which part of the sorted array is still being searched.

Q: What happens when the binary-search middle value equals the target?

When the value at the middle index equals the requested target, binary search ends because the element has been found. No further boundary changes or middle calculations are needed. If the values are not equal, their comparison determines which portion remains relevant, and the algorithm updates its tracked search region before calculating another middle position.

Q: Why can binary search outperform linear search on a sorted array?

Binary search uses the array's sorted order to discard a portion of the remaining search space after each middle comparison. Linear search instead may need to traverse nearly the whole array when the requested element appears near the end. The description states running times of O(log n) for binary search and O(n) for linear search.

Q: When might linear search find a value quickly?

Linear search can find a value quickly when that value appears near the beginning of the array. In the demonstrated sorted array, values such as 2 and 8 are encountered early, so sequential traversal requires few comparisons. However, searching for a later value such as 200 requires traveling through almost the entire array, which motivates using binary search when the data is sorted.

Summary & Key Takeaways

• Linear search traverses an array one element at a time. It can search either sorted or unsorted data because it does not rely on ordering. The process stops immediately when the target is found. If traversal reaches the end without a match, the algorithm reports that the requested element is absent.

• Binary search takes advantage of a sorted array by repeatedly reducing the active search space. It tracks low, high, and mid indices, compares the target with the middle element, and continues in the relevant portion. The book-page example illustrates why ordered data makes this narrowing process possible and efficient.

• The worked array example begins with low at index 0 and high at index 8, producing mid at index 4. When searching for 200, a middle value smaller than the target indicates that the search must continue toward the higher indices. Recalculating mid repeatedly narrows the remaining candidate region.