2.2.2 Searching Algorithms

Introduction

Searching algorithms are used to find a desired element that is available in some group of elements. Just like sorting, various searching methods are available. The two most common searching algorithms are Binary Search and Linear Search. Each has its own approach, requirements, and areas of best use.

Definition

Searching algorithms are methods used to locate a specific element (called the target or key) within a collection of elements (such as an array or list).

In simple words, searching means finding whether a particular item exists in a group, and if it does, finding its location.

Main Idea

Like sorting, various searching methods are available, for example:

• Binary Search algorithm
• Linear Search algorithm

• Whether the list is sorted or not
• The size of the list
• How frequently searches will be performed

Core Concept

• Binary Search works only on sorted lists and uses the divide and conquer approach — it repeatedly divides the list in half.
• Linear Search works on any list (sorted or unsorted) and checks each element one by one until the target is found.

Detailed Explanation

a) Binary Search Algorithm

This search method works on sorted lists. It follows the divide and conquer approach in which the sorted list is divided into two parts. The item to be searched is then compared with the middle element of the list. If it matches then, the location of the middle element is returned. Otherwise, we search into one of the divided parts depending upon the result produced in the last comparison.

Working of Binary Search

Consider the following sorted array of nine elements and we need to find a number 56.

Array: 10, 12, 24, 29, 39, 40, 51, 56, 69

Step 1: The item to be searched (56) is compared with the middle value (e.g. 39). We come to know that 56 is greater than 39, therefore the item is surely in the right side of the array (because the array is sorted).

Right part of the array: 40, 51, 56, 69

Step 2: It will again be divided into two parts. Considering 51 as the middle element, we will compare the item (56) with this. Because 56 is greater than 51, therefore we will again take right side of the array.

Right part of the array: 56, 69

Step 3: Divide the array again into two parts. Considering 56 as the middle element, we will compare it with the item to be searched (e.g. 56). Now, the required item is found.

Output: Location 7

If the required item is not found, the algorithm returns NULL.

Binary Search in Context of Computational Thinking

Abstraction: Search for a specific item in a sorted collection by repeatedly dividing the search space in half until the target item is found or the search space is empty. It efficiently narrows down the search space by half in each iteration.

• Middle Item Check: Examine the middle item to determine if it matches the target.
• Search Space Division: Divide the search space based on the comparison result.
• Recursive Process: Repeat the process on the narrowed down search space.

Algorithmic Design

• If it's equal to the target value, you're done.
• If it's greater than the target value, ignore the right half.
• If it's less than the target value, ignore the left half.

b) Linear Search Algorithm

This is a simple search algorithm; we go through the complete list and match the elements one-by-one until the required item is found. If the item is found, then the location of that element is returned, otherwise a NULL is returned. This search is also called as sequential search algorithm. However, there is no compulsion that the array should be sorted.

Working of Linear Search

Consider the given unsorted array and we need to find location of item 41.

Array: 70, 40, 30, 11, 57, 41, 25, 14, 56

Step 1: We will start from first element. The required item (41) is compared with the first element (70). Both don't match, we will go to next element.

Step 2: We will again compare the second element (e.g. 40) with required item (e.g. 41). Both don't match. So will continue the process.

Step 3: Continue comparing each element one by one until the target is found.

Step 4: We found the element at location 5. So output of this algorithm would be 5.

In these type of algorithms, if the required item is found we provide the output, or if item is not found and we reach at the end of array then a NULL is given in output.

Linear Search in Context of Computational Thinking

Abstraction: Search for a specific item in a collection by checking each item in order until the target item is found or the end of the collection is reached. It sequentially inspects each item until a match is found.

• Starting Point: Begin searching from the first item.
• Item Checking: Inspect each item to see if it matches the target.
• Stopping Condition: Stop when the target is found or the end of the collection is reached.

• Sequential Nature: The process involves moving through the collection one item at a time.
• Linear Progression: The search progresses linearly through the collection.
• Termination Condition: The search stops when the target is found or the entire collection is checked.

Algorithmic Design

Assume target value is the element that needs to be searched.

• Start from the beginning of the array.
• Check if the current element is equal to the target value.
• Repeat step 2 until the target value is found or you reach the end of the array.
• If you reach the end of the array without finding the target value, the target value is not in the array.

Linear Search vs Binary Search

The choice of searching algorithm depends on the specific requirements of your problem. However, following are some generic guidelines that could be helpful while selecting any searching algorithm:

Example — Movie Streaming:

Choosing a movie to watch from a list:

• Linear Search: Start from the top and scroll down until you find the movie.
• Binary Search: Divide the list in half, quickly narrowing down the options.

Algorithm Evaluation → Efficiency: The time it takes to find a movie reflects the efficiency of the search algorithm.

Intermediate Level

Comparison Table — Linear Search vs Binary Search

Why Binary Search is Faster

Binary Search eliminates half of the remaining elements with each comparison. For example:

• For 1000 elements, Binary Search needs at most about 10 comparisons.
• For 1,000,000 elements, Binary Search needs at most about 20 comparisons.
• Linear Search, in the worst case, would need to check all 1,000,000 elements.

This is why Binary Search is much faster for large arrays.

Why Linear Search is Still Useful

Linear Search is useful when:

• The list is not sorted (Binary Search cannot be used)
• The list is small
• You need to search only once (sorting first would take extra time)
• The list changes frequently (sorting after each change would be expensive)

How Binary Search Works — Step by Step

For a sorted array of n elements:

• Calculate mid = low + high2.
• If array[mid] == target, return mid.
• If array[mid] < target, set low = mid + 1.
• If array[mid] > target, set high = mid - 1.

How Linear Search Works — Step by Step

For an array of n elements:

• Start at index 0.
• Compare array[i] with target.
• If match, return i.
• If not match, increment i.
• Repeat until i reaches n or target is found.
• If target not found, return NULL.

Formula / Mathematical Form

Binary Search (conceptual):

``` Low = 0 High = n - 1 While Low ≤ High: Mid = Low + High2 If array[Mid] == target: Return Mid Else If array[Mid] < target: Low = Mid + 1 Else: High = Mid - 1 Return NULL ```

Linear Search (conceptual):

``` For i from 0 to n-1: If array[i] == target: Return i Return NULL ```

Solved Example

Example 1 — Binary Search for 29 in [10, 12, 24, 29, 39, 40, 51, 56, 69]

• Low = 0, High = 8, Mid = 4 (value 39). 29 < 39, search left half.
• Low = 0, High = 3, Mid = 1 (value 12). 29 > 12, search right half.
• Low = 2, High = 3, Mid = 2 (value 24). 29 > 24, search right half.
• Low = 3, High = 3, Mid = 3 (value 29). Match found at location 3.

Output: Location 3

Example 2 — Linear Search for 41 in [70, 40, 30, 11, 57, 41, 25, 14, 56]

• Compare 41 with 70: No
• Compare 41 with 40: No
• Compare 41 with 30: No
• Compare 41 with 11: No
• Compare 41 with 57: No
• Compare 41 with 41: Yes! Found at location 5.

Output: Location 5

Example 3 — Binary Search for 25 in [10, 12, 24, 29, 39, 40, 51, 56, 69]

• Low = 0, High = 8, Mid = 4 (value 39). 25 < 39, search left half.
• Low = 0, High = 3, Mid = 1 (value 12). 25 > 12, search right half.
• Low = 2, High = 3, Mid = 2 (value 24). 25 > 24, search right half.
• Low = 3, High = 3, Mid = 3 (value 29). 25 < 29, search left half.
• Low = 3, High = 2 → Loop ends.

Output: NULL (25 is not in the array)

Important Points

• - Searching algorithms are used to find a desired element in a group of elements.
• - Binary Search works on sorted lists and uses the divide and conquer approach.
• - Linear Search works on any list (sorted or unsorted) and checks each element one by one.
• - Binary Search is faster for large sorted lists.
• - Linear Search is suitable for small or unsorted lists.
• - Binary Search requires at most ⌈log₂(n)⌉ comparisons.
• - Linear Search requires at most n comparisons.
• - If the item is not found, both algorithms return NULL.

Remember

• - Binary Search: Sorted list, divide and conquer, compare with middle.
• - Linear Search: Check one by one, no sorting needed.
• - Binary Search requires sorted list.
• - Linear Search works on unsorted list.
• - Binary Search = fast for large lists.
• - Linear Search = simple, works on any list.
• - Both return NULL if item not found.
• - Binary Search comparisons: log₂(n)
• - Linear Search comparisons: n (worst case)

Common Mistakes

• - Using Binary Search on an unsorted list: Binary Search only works on sorted lists.
• - Forgetting to sort before Binary Search: Binary Search requires the list to be sorted first.
• - Assuming Linear Search is always slower: Linear Search is fine for small lists or when the list is unsorted.
• - Not considering efficiency: For large lists, the choice of algorithm matters a lot.
• - Mixing up the steps: In Binary Search, the list is divided in half; in Linear Search, elements are checked one by one.
• - Thinking Binary Search always finds the item in one step: Binary Search may require several comparisons before finding the item.
• - Confusing location with value: The output is the location (index) of the item, not the item itself.

Quick Revision

Searching algorithms are used to search for a desired element that is available in some group of elements.

• Works on sorted lists.
• Follows divide and conquer approach.
• Sorted list is divided into two parts.
• Item compared with middle element.
• If match, location of middle element is returned.
• Otherwise, search into one of the divided parts.
• Returns NULL if item not found.

• Simple search algorithm.
• Goes through the complete list.
• Matches elements one by one until the required item is found.
• If found, location is returned.
• If not found, NULL is returned.
• Also called sequential search.
• No compulsion that array should be sorted.

• Whether the list is sorted
• Size of the list
• Efficiency requirements

60-Second Revision

• Searching: Find a desired element in a group.
• Binary Search: Sorted list, divide and conquer, compare with middle.
• Linear Search: Check one by one, no sorting needed.
• Binary Search requires sorted list.
• Linear Search works on unsorted list.
• Binary Search: log₂(n) comparisons.
• Linear Search: n comparisons (worst case).
• Both return NULL if item not found.
• Warning: Never use Binary Search on an unsorted list.