Binary Search

 

What is Searching?

Searching is the process of finding a particular item (called key) from a collection of items (like an array, list, or database).

• If the item is found, we usually return its position (index).

• If the item is not found, we indicate that the search was unsuccessful.

Searching is very important in real-world applications like:

• Finding a name in a contact list 📞

• Searching a product on an online store 🛒

• Looking up a word in a dictionary 📖

---

🌟 What are Search Algorithms?

Search Algorithms are special methods or procedures to locate the target value within a dataset.

Common search algorithms include:

• Linear Search

• Binary Search

• Hashing-based Search

• Search Trees (like Binary Search Trees)

🌟 What is Binary Search?

Binary Search is an efficient search algorithm that finds the position of a target value in a sorted array.

• It divides the search space into two halves each time.

• It eliminates half of the remaining elements at every step.

• Works only when the array is sorted in ascending or descending order.

---

🌟 Idea Behind Binary Search

1. Start by comparing the middle element of the array with the target.

2. If the middle element is equal to the target → found ✅

3. If the target is smaller than the middle element → search left half.

4. If the target is greater than the middle element → search right half.

5. Repeat the process on the chosen half until you find the element or the range becomes empty.

---

📋 Binary Search Algorithm (Iterative)

1. Set two pointers:
   low = 0 (start index)
   high = n-1 (end index)

2. While low <= high:

   • Calculate mid = (low + high) / 2

   • If arr[mid] == key, return mid (element found).

   • Else if key < arr[mid], set high = mid - 1 (move to left half).

   • Else set low = mid + 1 (move to right half).

3. If low > high, element not found. Return -1.

---

📋 Binary Search Algorithm (Recursive)

1. If low > high, return -1 (element not found).

2. Calculate mid = (low + high)/2.

3. If arr[mid] == key, return mid.

4. If key < arr[mid], search in low to mid-1.

5. If key > arr[mid], search in mid+1 to high.

---

📈 Time Complexity

Case	Complexity
Best Case	O(1)
Average Case	O(log n)
Worst Case	O(log n)

• Much faster than linear search, especially for large datasets.

---

✏️ Example

Array:

[5, 10, 15, 20, 25, 30, 35]

Search for 20:

• low = 0, high = 6

• mid = (0+6)/2 = 3 → arr[3]=20

• Found at index 3 🎯

Search for 40:

• low = 0, high = 6

• mid = (0+6)/2 = 3 → arr[3]=20

• 40 >20 search in upper half

• low=mid+1=3+1=4  

• mid=(4+6)/2=5; arr[5]=30

• 40>30 search in upper half

• low=mid+1=5+1=6

• mid=(6+6)/2=6; arr[6]=35

• 40>35 search in upper half

• low=mid+1=6+1=7

• low >high stop;  element not found

Key Points

• Binary Search requires the array to be sorted.

• It is very efficient compared to linear search.

• Each comparison halves the search space!

C Program - Binary  Search

#include <stdio.h>

int binarySearch(int arr[], int n, int key) {

    int low = 0, high = n-1;

    

    while (low <= high) {

        int mid = (low + high) / 2;

        

        if (arr[mid] == key)

            return mid;

        else if (key < arr[mid])

            high = mid - 1;

        else

            low = mid + 1;

    }

    

    return -1; // Key not found

}

int main() {

    int arr[100], n, key, result;

    

    printf("Enter number of elements: ");

    scanf("%d", &n);

    

    printf("Enter sorted elements:\n");

    for (int i = 0; i < n; i++)

        scanf("%d", &arr[i]);

    

    printf("Enter the key to search: ");

    scanf("%d", &key);

    

    result = binarySearch(arr, n, key);

    

    if (result == -1)

        printf("Key not found.\n");

    else

        printf("Key found at index %d.\n", result);

    

    return 0;

}

C Program - Binary Search Recursive

#include <stdio.h>

// Recursive binary search function

int binarySearch(int arr[], int low, int high, int key) {

    if (low > high)

        return -1; // Key not found

    int mid = (low + high) / 2;

    if (arr[mid] == key)

        return mid;

    else if (key < arr[mid])

        return binarySearch(arr, low, mid - 1, key); // Search left half

    else

        return binarySearch(arr, mid + 1, high, key); // Search right half

}

int main() {

    int arr[100], n, key, result;

    printf("Enter number of elements: ");

    scanf("%d", &n);

    printf("Enter sorted elements:\n");

    for (int i = 0; i < n; i++)

        scanf("%d", &arr[i]);

    printf("Enter the key to search: ");

    scanf("%d", &key);

    result = binarySearch(arr, 0, n-1, key);

    if (result == -1)

        printf("Key not found.\n");

    else

        printf("Key found at index %d.\n", result);

    return 0;

}

Output

Enter number of elements: 5

Enter sorted elements:

6 7 8 9 10

Enter the key to search: 7

Key found at index 1.

Enter number of elements: 5

Enter sorted elements:

3 5 6 7 8 

Enter the key to search: 9

Key not found.