C++ Coding Test Course, Binary Search

Binary Search is an efficient method for finding a specific value in a sorted array. This algorithm has a time complexity of O(log n) because it repeatedly divides the array in half to find the target value. In this lecture, we will cover the basic concepts of binary search, implementation methods, and practical exercises using this technique.

Basic Principle of Binary Search

Binary search operates according to the following procedure:

Check the central element of the array.
Compare the central element with the target value:

If the target value is less than the central element, search in the left half of the array.
If the target value is greater than the central element, search in the right half of the array.
If the target value is equal to the central element, the search is complete.

This process is repeated until the target value is found.

Problem: Finding a Specific Value in a Sorted Array

Given an integer array arr and an integer target, write a program that returns the index of target. If target is not found, it should return -1.

Input Format

The first line contains the size of the array n. (1 ≤ n ≤ 10⁵)
The second line contains the sorted array arr in ascending order.
The third line contains the number target to be found.

Output Format

Print the index of the target. (An integer between 0 and n-1)

Example

Input:
    5
    1 3 5 7 9
    5

    Output:
    2

Solution Process

Step 1: Understanding the Problem

First, it is important to accurately understand the problem. Since we need to quickly find a specific element in a sorted array, we should use binary search.

Step 2: Implementing the Binary Search Algorithm

Let’s implement the binary search algorithm in C++.

#include <iostream>
#include <vector>

using namespace std;

int binarySearch(const vector<int> &arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;  // Found the target.
        } else if (arr[mid] < target) {
            left = mid + 1;  // Move to the right half.
        } else {
            right = mid - 1;  // Move to the left half.
        }
    }
    return -1;  // Target not found.
}

int main() {
    int n;
    cout << "Enter the size of the array: ";
    cin >> n;
    
    vector<int> arr(n);
    cout << "Enter the elements of the array: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    int target;
    cout << "Enter the number you want to find: ";
    cin >> target;

    int result = binarySearch(arr, target);
    if (result != -1) {
        cout << "Index of the target: " << result << endl;
    } else {
        cout << "Target not found." << endl;
    }

    return 0;
}

Step 3: Code Explanation

– The binarySearch function takes an integer vector and a target value as input and returns the index of the target value.
– left and right represent the start and end indices of the search interval.
– The while loop runs while left is less than or equal to right.
– In each iteration, the central index mid is computed, and the central element is compared with the target value to determine the next search interval.

Step 4: Testing and Verification

After writing the code, it is essential to run it against various test cases to ensure it returns the correct results. Consider the following tests:

When the target value exists in the array
When the target value does not exist in the array
When the array size is 1
When there are duplicate elements

Conclusion

Binary search is a very useful algorithm, especially as it exhibits excellent performance in terms of speed when working with sorted arrays. In this lecture, we understood the basic principles of binary search and implemented actual code. Mastering binary search will greatly help in solving many other algorithm problems.

In the next lecture, we will cover variations of binary search and various applications. I encourage you to enhance your algorithm skills through continuous learning!