Search

binary search by ON August 18 2019

Binary search is a searching technique that finds the position of a target value within a sorted list. In this searching technique target element match the middle value of the list if not found then it moves to the half of the list and the half list is eliminated on which cannot lie. Again search the element in the remaining half list and this process continues to repeat till the target value is found or declare an element do not exist.

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

int binarySearch(int arr[], int left, int right, int key)
{
    if (right >= left) {
        int mid = left + (right - left) / 2;

        // If the element is present at the middle itself.
        if ( arr[mid] == key ) {
            return mid;
        }

        // If element is smaller than find in left side.
        if ( arr[mid] > key ){
            return binarySearch(arr, left, mid - 1, key);
        }

        // else element in right side.
        return binarySearch(arr, mid + 1, right, key);
    }

    //If key is not exist in array.
    return -1;
}

int main() {

    // Array of elements.
    int arr[] = {1,4,7,11,16,19,23,28,30,31,40,78,105,201};

    // Length of array
    int arrayLength = sizeof( arr ) / sizeof( arr[0] );

    // Key that need to find in array.
    int key = 201;

    int index = binarySearch( arr, 0, arrayLength - 1, key );

    if ( index != -1 ) {
        cout<<"Found element at position : "<<index<<endl;
    } else {
        cout<<"Given element is not exist in array"<<endl;
    }

    return 0;
}

Key Points:

  • Binary search is also known as a half-interval search, logarithmic search or binary chop.
  • This search algorithm works on the principle of divide and conquer.
  • Binary search is worked with a sorted list.
  • The time complexity of this searching technique is O( log n ).
  • Binary search is faster than linear and jump search.
author's avatar ALL POST
Knowledge contribution is better than any contribution.

RELATED POST


1. linear search

BY August 18 2019

2. What is Jump search

BY August 18 2019
LEAVE A COMMENT

Leave a Reply

Your e-mail address will not be published. Required fields are marked *