Binary Search

Introduction

Binary search is a searching algorithm, used to search for an element in an array. It follows a unique approach which reduces the time complexity as compared to linear search. However, to use binary search, the array must be sorted.

Implementation

Let us see how to implement binary search in Java:

        //let element to be found=target
		int low=0;
		int high=n-1; //where n is the length of the sorted array
        int mid; //represents the mid index of the array

        int flag=0; //element not yet found 

		while(low<=high) {

			mid=(low + high)/2;
			if(arr[mid]==target) {
				flag=1; //element found
				System.out.println("Target found!");
				break;
			}
			else if(arr[mid]<target) {
                // which means target is to the right of mid element
				low=mid+1;
			}
			else {
                //target is to the left of mid element
				high=mid-1;
			}
			
		}

		if(flag==0) {
			System.out.println("Target not found!");
		}

Implementation

Let us see how to implement binary search in c++:\

#include <iostream>
#include <vector>

void binarySearch(const std::vector<int>& arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    int mid;
    bool found = false; // element not yet found

    while (low <= high) {
        mid = low + (high - low) / 2; // to avoid potential overflow
        if (arr[mid] == target) {
            found = true; // element found
            std::cout << "Target found!" << std::endl;
            break;
        }
        else if (arr[mid] < target) {
            // target is to the right of mid element
            low = mid + 1;
        }
        else {
            // target is to the left of mid element
            high = mid - 1;
        }
    }

    if (!found) {
        std::cout << "Target not found!" << std::endl;
    }
}

int main() {
    std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9}; // example sorted array
    int target = 5; // example target

    binarySearch(arr, target);

    return 0;
}

In this algorithm, the searching interval of the array is divided into half at every iteration until the target is found. This results in lesser comparisions and decreases the time required.

Time complexity:

Linear/Sequential search: O(n)
Binary search : O(log n)

Points to Remember:

• Binary search requires a sorted array.
• Works for 1 dimensional arrays.
• Faster and complex than sequential search.
• Uses the divide and conquer approach.
• Best if arrays are too long (large datasets).