Data Structures - Binary Search Algorithm

Basic programming - Binary Search

Question:

Given a sorted array arr[] of n elements, write a function to search a given element x in arr[].

Example:

Input: arr[] = {1, 4, 6, 7, 9, 11, 12, 15, 17}
   x = 12;
Output: 6
Explanation: Element x is represented at index 6, and the program only runs 2 times. First, middle value is 9. Second, middle value is 12.

The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Log n).

Source code:

Version

Idea:
You should know the length of array first, repeatedly dividing the search interval in half is at the core of binary search.
The demonstration is shown as below:

Hence, you can declare head variable that is index 0, and tail varialbe that is index n - 1 (n is the length of array). Therefore, the middle of the interval is (head + tail) / 2

At 14 line, if the value of middle is bigger than the target, narrow the interval to the lower half. Otherwise, narrow it to the upeer half.

Repeat 10 - 18 line to find the position of target until head's index is bigger than tail's index, it means the target isn't exist in array, so return -1.

Time complexity: O(log n)

#include <iostream>
#include <vector>

using namespace std;

int binarySearch(vector<int> arr, int input){
    const int n = arr.size();
    int head = 0, tail = n - 1, middle = - 1;
    
    while(head <= tail){
        middle = (head + tail) / 2;
        if(arr[middle] == input) return middle;
        
        if(arr[middle] >input){
            tail = middle - 1;
        }else{
            head = middle + 1;
        }
    }
    return -1;
}

int main()
{
    vector<int> arr{ 2, 3, 4, 7, 10, 15, 22, 30, 33, 40};
    int x = 22;
    int res = binarySearch(arr, x);
    (res == -1)?cout << "Input is not exist in array":cout << "Index " << res << " is " << arr[res];

    return 0;
}