searching

Table of Contents

1. Search Algorithms
   • Binary Search
   • Linear Search

---

Search Algorithms

Binary Search

Question: How do you perform a binary search on a sorted array?

Code Explanation:

#include<bits/stdc++.h>
using namespace std;

void binarySearch(vector<int> arr, int key) {
    int l = 0, r = arr.size() - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == key) {
            cout << "found at index " << mid << endl;
            return;
        } else if (arr[mid] >= key) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
}

int main() {
    vector<int> arr = {6, 7, 5, 8, 88, 34, 1, 9};
    sort(arr.begin(), arr.end());
    for (int i : arr) cout << i << " ";
    binarySearch(arr, 88);
}

Explanation:

• Purpose: The function implements the binary search algorithm on a sorted array.
• Sorting: The input array is first sorted using the sort() function.
• Logic: The algorithm maintains two pointers, l and r, representing the left and right bounds of the array. It repeatedly calculates the middle index (mid) and compares the value at mid with the search key.
  • If the key is found, it prints the index.
  • If the middle element is greater than the key, it narrows the search to the left half (r = mid - 1).
  • Otherwise, it narrows the search to the right half (l = mid + 1).
• Efficiency: The time complexity of binary search is O(log n) due to the division of the search space by half in each step.

---

Linear Search

Question: How do you perform a linear search on an array?

Code Explanation:

#include<iostream>
using namespace std;

void linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            cout << "found at index " << i << endl;
            return;
        }
    }
}

int main() {
    int n, key;
    n = 10;
    int arr[10];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cin >> key;
    linearSearch(arr, n, key);    
    return 0;
}

Explanation:

• Purpose: The function performs a linear search on an array to find a specific element.
• Logic: It iterates through the array one element at a time and checks if the current element matches the search key.
  • If the key is found, it prints the index and exits the loop.
  • If the loop completes without finding the key, the function doesn't return any value, implying the key is not present in the array.
• Efficiency: The time complexity of linear search is O(n), as each element is checked individually.