the simple searching algorithm for searching an element in array is Linear Search and the time complexity for linear search is o(n).

Binary search is one of the fundamental algorithms in computer science. and an effective algorithm as compared to linear search .

Binary search algorithm in C++ relies on a divide and conquer strategy to find a value within an already-sorted collection.

Finding a value in a sorted sequence
In its simplest form, binary search is used to quickly find a value in a sorted sequence (consider a sequence an ordinary array for now).

We’ll call the sought value the target value for clarity. Binary search maintains a contiguous sub sequence of the starting sequence where the target value is surely located.

This is called the search space. The search space is initially the entire sequence. At each step, the algorithm compares the median value in the search space to the target value. Based on the comparison and because the sequence is sorted, it can then eliminate half of the search space. By doing this repeatedly, it will eventually be left with a search space consisting of a single element, the target value.

For example, consider the following sequence of integers sorted in ascending order and say we are looking for the number 55:

0 5 13 19 22 41 55 68 72 81 98

We are interested in the location of the target value in the sequence so we will represent the search space as indices into the sequence. Initially, the search space contains indices 1 through 11. Since the search space is really an interval, it suffices to store just two numbers, the low and high indices. As described above, we now choose the median value, which is the value at index 6 (the midpoint between 1 and 11): this value is 41 and it is smaller than the target value. From this we conclude not only that the element at index 6 is not the target value, but also that no element at indices between 1 and 5 can be the target value, because all elements at these indices are smaller than 41, which is smaller than the target value. This brings the search space down to indices 7 through 11:

55 68 72 81 98

Proceeding in a similar fashion, we chop off the second half of the search space and are left with:

55 68

Depending on how we choose the median of an even number of elements we will either find 55 in the next step or chop off 68 to get a search space of only one element. Either way, we conclude that the index where the target value is located is 7.

If the target value was not present in the sequence, binary search would empty the search space entirely. This condition is easy to check and handle. Here is some code to go with the description:

binary_search(A, target):
   lo = 1, hi = size(A)
   while lo <= hi:
      mid = lo + (hi-lo)/2
      if A[mid] == target:
         return mid            
      else if A[mid] < target: 
         lo = mid+1
      else:
         hi = mid-1
            
   // target was not found

Complexity

binary search will never use more than (in big-oh notation) O(log N) comparisons to find the target value.

The logarithm is an awfully slowly growing function. In case you’re not aware of just how efficient binary search is, consider looking up a name in a phone book containing a million names. Binary search lets you systematically find any given name using at most 21 comparisons.

Capture.PNG

Important Points:

  • always use binary search with sorted values.
  • Time complexity of binary search:
    • Best case performance o(1).
    •  average and worst case time complexity o(logn).

 

#include <cstdlib>
#include <iostream>
using namespace std;

int binary_search(int array[], int first, int last, int value);

int main() {

 int list [10] = { 1, 3, 4, 5, 7, 9, 12, 14, 26, 30 };
 int min = 0;
 int max = sizeof(list) - 1;
 int result = binary_search(list, min, max, 9);

 if (result >= 0)
     cout << "Binary search results: " << result << endl;
 else
      cout << "Not Found" << endl;
 return 0;
}
int binary_search(int array[], int first, int last, int search_key)
{
  int index;
  if (first > last)
      index = -1;
  else {
          int mid = first + (last - first) / 2;
          if (search_key == array[mid])
              index = mid;
          else
              if (search_key < array[mid])
                 index = binary_search(array, first, mid - 1, search_key);
              else
                 index = binary_search(array, mid + 1, last, search_key);
  } 
 return index;
}

 

Advertisements