Binary Search

Sumit included in DSA

30-11-2023 1100 words 6 minutes

Contents

Note

Use the table of contents to navigate to the portion that you are interested in.

Introduction

We know that there is two type of searching technique 1.Linear Search and 2.Binary Search. Here we discus only about binary search. Binary search is a searching technique, it is used to locate a specific element with in the sorted array.

Warning

It is applicable only on monotonic function which means values should be in the increasing or decreasing order.

Time Complexity:

Option	Description
Best Case:	O(1)
Average Case:	O(log N)
Worst Case:	O(log N)

Space Complexicity:

Option	Description
Best Case:	O(1)

Creation of Function

First initialise start and end indices to the first and last element of the array respectively. then calculate the middle index by (start+end)/2. Inside the while loop, compare the value of mid with the key until the start index becomes less than or equal to the end index. Here three cases arises.

Case 1: If the key matches with the mid element it returns the mid element.

Case 2: If the key is greater than the mid element then we have to check the right part of the array for that we have to initialise the start as mid + 1.

Case 3: If the key is less than the mid element than we have to check the left part of the array for that we have to update the end as mid - 1.

Tip

use mid= start + (end-start)/2 instead of (start+end)/2.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


#include<iostream> 
using namespace std;

int binarysearch(int arr[], int size, int key)
{
    int start =0;
    int end = size-1;
    //int mid= (start+end)/2;
    int mid= start + (end-start)/2;
    while(start <= end){
        if(arr[mid] == key){
            return mid;
        }
        if(key> arr[mid]){  //go to right part
            start= mid +1 ;
        }
        else{
            end= mid - 1;   //go to left part
        }
        //mid= (start+end)/2;
        mid = start + (end-start)/2;
    }
    return -1;
}

The Main Function

Now we check the code for both if the number of elements in the array is even or odd. In the main function we define two arrays 1st is even array and the 2nd one is odd array. After that we call the function and store the result in evenindex for even array and in oddindex for odd array after that we print the indexes. Here we see that our function works properly for both cases. We can see the output.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


int main()
{
    int even[6]= {2,4,6,8,12,18};
    int odd[5]= {3,8,11,14,16};

    int evenindex= binarysearch(even, 6, 6);
    cout<<"index of 6 is "<<evenindex << endl;

    int oddindex= binarysearch(odd, 5, 14);
    cout<<"index of 14 is "<<oddindex << endl;


    return 0;
}

Output

We got the right output for both cases.

Complete Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


#include<iostream> 
//it applicable only on monotonic function values should be in inc or dec order.
using namespace std;
int binarysearch(int arr[], int size, int key)
{
    int start =0;
    int end = size-1;
    //int mid= (start+end)/2;
    int mid= start + (end-start)/2;
    while(start <= end){
        if(arr[mid] == key){
            return mid;
        }
        //go to right part
        if(key> arr[mid]){
            start= mid +1 ;
        }
        else{
            end= mid - 1;
        }
        //mid= (start+end)/2;
        mid = start + (end-start)/2;
    }
    return -1;
}

int main(){
    int even[6]= {2,4,6,8,12,18};
    int odd[5]= {3,8,11,14,16};
    int evenindex= binarysearch(even, 6, 6);
    cout<<"index of 6 is "<<evenindex << endl;
    int oddindex= binarysearch(odd, 5, 14);
    cout<<"index of 14 is "<<oddindex << endl;
    return 0;
}  

Advantages & Drawbacks

Advantages

faster than linear search
More efficient
Minimal memory requirement
Easy to understand and implement
More efficient for large dataset

Drawbacks

The array should be sorted.
Not suitable for unordered lists
Inefficient for small dataset
Not adaptive for changes
Limited to static dataset

Applications

Database searching
Finding elements in a array
Used in file system to search a specific file
In machine learning
In Game development

Problems

First and Last position of an element in sorted array solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74



// pair <int, int> p;
//     p.first = 5;
//     p.second = 6;


#include<iostream>
using namespace std;


int firstOccurance(int arr[], int n, int key){
    int start = 0;
    int end = n-1;
    int mid = start +(end-start)/2;
    int ans = -1;
    while(start <= end)
    {
        if (arr[mid]== key)
        {
            ans = mid;
            end = mid - 1;
        }
        else if (arr[mid] < key)
        {   // go to right part
            start = mid + 1;
        }
        else if (arr[mid] > key)
        {   // go to left part
            end = mid -1;
        }
        mid = start + (end - start)/2;
    }
    return ans;
}

int lastOccurance(int arr[], int n, int key){
    int start = 0;
    int end = n-1;
    int mid = start +(end-start)/2;
    int ans = -1;
    while(start <= end)
    {
        if (arr[mid]== key)
        {
            ans = mid;
            start = mid + 1;
        }
        else if (arr[mid] < key)
        {   // go to right part
            start = mid + 1;
        }
        else if (arr[mid] > key)
        {   // go to left part
            end = mid -1;
        }
        mid = start + (end - start)/2;
    }
    return ans;
}

pair<int , int> firstAndLastOccurance(int arr[], int n, int key){
    pair<int , int > p;
    p.first = firstOccurance(arr , n, key);
    p.second = lastOccurance(arr , n , key);
    return p;

}

int main() {
    int arr[9]={1,2,3,3,3,3,3,4,5};
    cout << " first occurace of 3 is index " << firstOccurance(arr, 9 , 3) << endl;
    cout << " last occurace of 3 is index " << lastOccurance(arr, 9 , 3) << endl;
    firstAndLastOccurance(arr, 9, 3);
}

Fun Dose

<div style="position: relative; padding-bottom: 56.25%; height: 0; overflow: hidden;">
  <iframe allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen="allowfullscreen" loading="eager" referrerpolicy="strict-origin-when-cross-origin" src="https://www.youtube-nocookie.com/embed/FMzj9UYHTPQ?autoplay=0&controls=1&end=0&loop=0&mute=0&start=0" style="position: absolute; top: 0; left: 0; width: 100%; height: 100%; border:0;" title="YouTube video"
  ></iframe>
</div>