Skip to main content

Binary Search Algorithm!


Binary search is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(log N)¹. 

Here's how it works:
1. Compare x with the middle element.
2. If x matches with the middle element, we return the mid index.
3. Else If x is greater than the mid element, then x can only lie in the right half subarray after the mid element. So we recur for the right half.
4. Else (x is smaller) recur for the left half.

This process continues until the element is found or the subarray is empty.

Look at the array, it is sorted and if we want to find 7 in this array easily by implementing binary search algorithm. We can find it in O(logn) time. While a linear search will take O(n)
time which is very long time. So, if an array is sorted we always use Binary search.

Algorithm:

int main()
{
    optimize();
    int arr[]= {1,4,5,8,10,26};
    int n = sizeof(arr)/sizeof(arr[0]);
    int st=0,en=n-1;
    int target = 8;
    while(st<=en)
    {
        int k = st + (en-st)/2;
        if(arr[k]>target) en = k-1;
        else if(arr[k]<target) st = k+1;
        else{
            cout<<k+1<<endl;
            break;
        }
    }
    return 0;
}

Time complexity: O(n)

STL:

int n = binary_search(sortedarray.begin(), sortedarray.end(), target);

That function will return 1, if target element is present in the array. Otherwise, it will return 0.





Labels:

Comments

Post a Comment

Popular posts from this blog

Rotated Array(Modified Binary Search)

  A modified binary search is an algorithm that can be used to find an element in a sorted array by using a different base or condition than the standard binary search. It is an extension of the bitwise binary search and has a similar running time of O(log N) . There are different ways to modify the binary search algorithm, such as using a different number base, finding the minimum element in a rotated and sorted array, or comparing the input element with the first, last and middle elements of the array. Today we will look at rotated array problems. A rotated array is an array that is sorted in ascending order but shifted to the right by some unknown number of positions. For example, [0,1,2,4,5,6,7] is a sorted array and [4,5,6,7,0,1,2] is a rotated array with 4 positions shifted. A rotated array can also be seen as two sorted subarrays concatenated together. For example, [4,5,6,7] and [0,1,2] are two sorted subarrays that form the rotated array [4,5,6,7,0,1,2]. There are two very ...
Post a Comment
Read more

Two Pointer Problems

Here we have given some important two pointer problems below: 1. Valid Palindrome: A phrase is a  palindrome  if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. Given a string  s , return  true  if it is a  palindrome , or  false  otherwise .  -> Solution: class Solution { public:     bool isPalindrome(string s) {       int low=0;       int high=s.length()-1;       while(low<high){           while(!iswalnum(s[low]) && low<high){               low++;           }           while(!iswalnum(s[high]) && low<high){               high--;           } ...
Post a Comment
Read more

Find out all divisor in efficient way!

1. Brute force approach:   In this process, we use a for loop and iterate the whole 1 to n number. Then, we find out all the divisors by one by one. It is not a optimal solution for this problem. Because, it will take O(n) time to find out all divisors. int main() {     optimize();     ll n;     cin>>n;     for(ll i=1; i<=n; i++)     {         if(n%2==0) cout<<i<<" ";     }     cout<<endl;     return 0; } Time complexity: O(n) 2. SQRT approach:   In this process, we only iterate in the loop by half of the numbers. Because, if we see we don't need to go through whole n numbers. int main() {     optimize();     ll n;     cin>>n;     for(ll i=1; i * i<=n; i++)     {         if(n%2==0) cout<<i<<" "<<n/i<<endl;     }     return 0; } Tim...
Post a Comment
Read more