# Binary Search

If we have an <mark style="color:red;">**array**</mark> that is <mark style="color:red;">**sorted**</mark>, we can use a much more <mark style="color:red;">**efficient algorithm**</mark> called a <mark style="color:red;">**Binary Search**</mark>. In binary search <mark style="color:red;">**each time**</mark> we <mark style="color:red;">**divide array**</mark> into <mark style="color:red;">**two equal half**</mark> and <mark style="color:red;">**compare middle element**</mark> with <mark style="color:red;">**search element**</mark>.

#### Searching Logic

* If <mark style="color:red;">**middle element**</mark> is <mark style="color:red;">**equal to search element**</mark> then we got that element and <mark style="color:red;">**return that index**</mark>
* If <mark style="color:red;">**middle element**</mark> is <mark style="color:red;">**less than search element**</mark> we <mark style="color:red;">**look right part**</mark> of array
* If <mark style="color:red;">**middle element**</mark> is <mark style="color:red;">**greater than search element**</mark> we <mark style="color:red;">**look left part**</mark> of array.

### The complexity of Binary Search Technique

* **Time Complexity:** O(1) for the best case. O(log2 n) for average or worst case.
* **Space Complexity:** O(1)&#x20;

### Binary Search - Algorithm

![](https://3717782766-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F60gGuq3OlHvCAPS1ajFy%2Fuploads%2FdMKv67syl4Q2TYmbzJ4n%2Fimage.png?alt=media\&token=ee27e30c-5dfa-4dfb-a0f4-f119de8d1736)

### Binary Search - Example

#### Search for <mark style="color:red;">**6**</mark> in given array

![](https://3717782766-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F60gGuq3OlHvCAPS1ajFy%2Fuploads%2FdQ314gaGn2Bk1zowzqjY%2Fimage.png?alt=media\&token=af4fa6ba-71c3-4a75-828d-91a6128fe572)

![](https://3717782766-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F60gGuq3OlHvCAPS1ajFy%2Fuploads%2FTfezrpCShvMrQMgS9BjQ%2Fimage.png?alt=media\&token=e4e751c6-fb22-49b4-9784-c1090f65d4a2)

![](https://3717782766-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F60gGuq3OlHvCAPS1ajFy%2Fuploads%2FI9GrKofbWUI5CotEJPfA%2Fimage.png?alt=media\&token=ba92d3e7-3bbb-4cd3-b868-869b4b7473bf)

### Example:

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

int binarySearch(int a[], int start, int end, int key) {
   if(start <= end) {
      int mid = (start + (end - start) /2); //mid location of the list
      if(a[mid] == key)
         return mid;
      if(a[mid] > key)
         return binarySearch(a, start, mid-1, key);
         return binarySearch(a, mid+1, end, key);
   }
   return -1;
}

int main() {
   int n, skey, loc;
   cout << "Enter number of items: ";
   cin >> n;

   int arr[n]; 
   cout << "Enter items: " << endl;

   for(int i = 0; i< n; i++) {
      cin >> arr[i];
   }

   cout << "Enter which element to search in the list: ";
   cin >> skey;

   if((loc = binarySearch(arr, 0, n, skey)) >= 0)
      cout << "Item found at location: " << loc << endl;
   else
      cout << "Item is not found in the list." << endl;
}
```

### Output

```
Enter number of items: 10
Enter items:
-1 5 6 18 19 25 46 78 102 114
Enter which element to search in the list: 6
Item found at location: 2
```