# Binary Search

{% embed url="<https://codepen.io/bgoonz/pen/MWbZoOa>" %}

#### In a nutshell, this search algorithm takes advantage of a collection of elements that is already sorted by ignoring half of the elements after just one comparison.

* [ ] ***Compare x with the middle element.***
* [ ] ***If x matches with the middle element, we return the mid index.***
* [ ] ***Else if x is greater than the mid element, then x can only lie in the right (greater) half subarray after the mid element. Then we apply the algorithm again for the right half.***
* [ ] ***Else if x is smaller, the target x must lie in the left (lower) half. So we apply the algorithm for the left half.***

Pseudo Code Algorithm:

{% hint style="info" %}
parameter list: a list of sorted value parameter target: the value to search for
{% endhint %}

{% hint style="info" %}

> if the list has zero length, then return false
> {% endhint %}

{% hint style="info" %}

> determine the slice point: if the list has an even number of elements, the slice point is the number of elements divided by two if the list has an odd number of elements, the slice point is the number of elements minus one divided by two
> {% endhint %}

{% hint style="info" %}

> create an list of the elements from 0 to the slice point, not including the slice point, which is known as the "left half" create an list of the elements from the slice point to the end of the list which is known as the "right half"
> {% endhint %}

{% hint style="info" %}

> if the target is less than the value in the original array at the slice point, then return the binary search of the "left half" and the target
> {% endhint %}

{% hint style="info" %}

> if the target is greater than the value in the original array at the slice point, then return the binary search of the "right half" and the target
> {% endhint %}

{% hint style="info" %}

> if neither of those is true, return true
> {% endhint %}

>

![](https://blog.penjee.com/wp-content/uploads/2015/04/binary-and-linear-search-animations.gif)

###

## Recursive Binary Search

```python
# Python 3 program for recursive binary search.
# Modifications needed for the older Python 2 are found in comments.

# Returns index of x in arr if present, else -1
def binary_search(arr, low, high, x):

    # Check base case
    if high >= low:

        mid = (high + low) // 2

        # If element is present at the middle itself
        if arr[mid] == x:
            return mid

        # If element is smaller than mid, then it can only
        # be present in left subarray
        elif arr[mid] > x:
            return binary_search(arr, low, mid - 1, x)

        # Else the element can only be present in right subarray
        else:
            return binary_search(arr, mid + 1, high, x)

    else:
        # Element is not present in the array
        return -1

# Test array
arr = [ 2, 3, 4, 10, 40 ]
x = 10

# Function call
result = binary_search(arr, 0, len(arr)-1, x)

if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in array")
```

### Itterative Binary Search:

```python
# Iterative Binary Search Function
# It returns index of x in given array arr if present,
# else returns -1
def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0

    while low <= high:

        mid = (high + low) // 2

        # If x is greater, ignore left half
        if arr[mid] < x:
            low = mid + 1

        # If x is smaller, ignore right half
        elif arr[mid] > x:
            high = mid - 1

        # means x is present at mid
        else:
            return mid

    # If we reach here, then the element was not present
    return -1


# Test array
arr = [ 2, 3, 4, 10, 40 ]
x = 10

# Function call
result = binary_search(arr, x)

if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in array")
```

```python
# Uses python3
import random
"""You're going to write a binary search function.
You should use an iterative approach - meaning
using loops.
Your function should take two inputs:
a Python list to search through, and the value
you're searching for.
Assume the list only has distinct elements,
meaning there are no repeated values, and
elements are in a strictly increasing order.
Return the index of value, or -1 if the value
doesn't exist in the list."""

def binary_search(input_array, value):
    test_array = input_array
    current_index = len(input_array)//2
    input_index = current_index

    found_value = test_array[current_index]
    while(len(test_array)>1 and found_value!=value):
        if(found_value<value):
            test_array = test_array[current_index:]
            current_index = len(test_array)//2
            input_index += current_index
            found_value = input_array[input_index]
        else:
            test_array = test_array[0:current_index]
            current_index = len(test_array)//2
            # divmod needed to be used instead of round() since the behavior
            # for .5 changed from rounding up to rounding down in Python 3
            q, r = divmod(len(test_array), 2.0)
            input_index = int(input_index - q - r)
            found_value = input_array[input_index]
    else:
        if(found_value==value):
            return input_index

    return -1

def linear_search(a, x):
    for i in range(len(a)):
        if a[i] == x:
            return i
    return -1

# compare naive algorithm linear search vs. binary search results
def stress_test(n, m):
    test_cond = True
    while(test_cond):
        a = []
        for i in range(n):
            a.append(random.randint(0, 10**9))
        a.sort()
        for i in range(m):
            b = random.randint(0, n-1)
            print([linear_search(a, a[b]), binary_search(a, a[b])])
            # stops if the searches do not give identical answers
            if(linear_search(a, a[b]) != binary_search(a, a[b])):
                test_cond = False
                print('broke here!')
                break



stress_test(100, 100000)



#test_list = [1,3,9,11,15,19,29, 35, 36, 37]
#test_val1 = 25
#test_val2 = 15
#print(binary_search(test_list, test_val1))
#print(binary_search(test_list, test_val2))
#print(binary_search(test_list, 11))
```

```python
# given array a and need to find value x
# left and right correspond to initial indices of array a bounding the search
# segment of array a above and below, respectively
def binary_search_recursive(a, x, left=0, right=(len(a)-1)):
"""Recursive Binary Search algorithm implemented using list indexing"""
    index = (left+right)//2
    if a[index]==x:
        return index
    elif x>(a[right]) or x<a[left]: # first case where x is not in the list!
        return -1
    elif left==right: # case where search is complete and no value x not found
        return -1
    elif left==right-1: # case where there are only two numbers left, check both!
        left = right
        return binary_search_recursive(a, x, left, right)
    elif a[index]<x:
        left = index
        return binary_search_recursive(a, x, left, right)
    elif a[index]>x:
        right = index
        return binary_search_recursive(a, x, left, right)
```

### Binary Search Recursive:

```python
def binarySearch(arr, searchValue):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < searchValue:
            low = mid + 1
        elif arr[mid] > searchValue:
            high = mid - 1
        else:
            return True

    return False


def binarySearchRec(arr, search_value):
    if len(arr) == 0:
        return False
```

```python
"""
Given an array where elements are sorted in ascending order,
convert it to a height balanced BST.
"""


class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


def array_to_bst(nums):
    if not nums:
        return None
    mid = len(nums) // 2
    node = TreeNode(nums[mid])
    node.left = array_to_bst(nums[:mid])
    node.right = array_to_bst(nums[mid + 1 :])
    return node
```

```python
"""
Implement Binary Search Tree. It has method:
    1. Insert
    2. Search
    3. Size
    4. Traversal (Preorder, Inorder, Postorder)
"""

import unittest


class Node(object):
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


class BST(object):
    def __init__(self):
        self.root = None

    def get_root(self):
        return self.root

    """
        Get the number of elements
        Using recursion. Complexity O(logN)
    """

    def size(self):
        return self.recur_size(self.root)

    def recur_size(self, root):
        if root is None:
            return 0
        else:
            return 1 + self.recur_size(root.left) + self.recur_size(root.right)

    """
        Search data in bst
        Using recursion. Complexity O(logN)
    """

    def search(self, data):
        return self.recur_search(self.root, data)

    def recur_search(self, root, data):
        if root is None:
            return False
        if root.data == data:
            return True
        elif data > root.data:  # Go to right root
            return self.recur_search(root.right, data)
        else:  # Go to left root
            return self.recur_search(root.left, data)

    """
        Insert data in bst
        Using recursion. Complexity O(logN)
    """

    def insert(self, data):
        if self.root:
            return self.recur_insert(self.root, data)
        else:
            self.root = Node(data)
            return True

    def recur_insert(self, root, data):
        if root.data == data:  # The data is already there
            return False
        elif data < root.data:  # Go to left root
            if root.left:  # If left root is a node
                return self.recur_insert(root.left, data)
            else:  # left root is a None
                root.left = Node(data)
                return True
        else:  # Go to right root
            if root.right:  # If right root is a node
                return self.recur_insert(root.right, data)
            else:
                root.right = Node(data)
                return True

    """
        Preorder, Postorder, Inorder traversal bst
    """

    def preorder(self, root):
        if root:
            print(str(root.data), end=" ")
            self.preorder(root.left)
            self.preorder(root.right)

    def inorder(self, root):
        if root:
            self.inorder(root.left)
            print(str(root.data), end=" ")
            self.inorder(root.right)

    def postorder(self, root):
        if root:
            self.postorder(root.left)
            self.postorder(root.right)
            print(str(root.data), end=" ")


"""
    The tree is created for testing:

                    10
                 /      \
               6         15
              / \       /   \
            4     9   12      24
                 /          /    \
                7         20      30
                         /
                       18
"""


class TestSuite(unittest.TestCase):
    def setUp(self):
        self.tree = BST()
        self.tree.insert(10)
        self.tree.insert(15)
        self.tree.insert(6)
        self.tree.insert(4)
        self.tree.insert(9)
        self.tree.insert(12)
        self.tree.insert(24)
        self.tree.insert(7)
        self.tree.insert(20)
        self.tree.insert(30)
        self.tree.insert(18)

    def test_search(self):
        self.assertTrue(self.tree.search(24))
        self.assertFalse(self.tree.search(50))

    def test_size(self):
        self.assertEqual(11, self.tree.size())


if __name__ == "__main__":
    unittest.main()
```

## Delete Node

```python
"""
Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

Search for a node to remove.
If the node is found, delete the node.
Note: Time complexity should be O(height of tree).

Example:

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

    5
   / \
  4   6
 /     \
2       7

Another valid answer is [5,2,6,null,4,null,7].

    5
   / \
  2   6
   \   \
    4   7
"""


class Solution(object):
    def delete_node(self, root, key):
        """
        :type root: TreeNode
        :type key: int
        :rtype: TreeNode
        """
        if not root:
            return None

        if root.val == key:
            if root.left:
                # Find the right most leaf of the left sub-tree
                left_right_most = root.left
                while left_right_most.right:
                    left_right_most = left_right_most.right
                # Attach right child to the right of that leaf
                left_right_most.right = root.right
                # Return left child instead of root, a.k.a delete root
                return root.left
            else:
                return root.right
        # If left or right child got deleted, the returned root is the child of the deleted node.
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        else:
            root.right = self.deleteNode(root.right, key)
        return root
```

## Another:

```python
def binary_search(arr, x):
    start= 0
    end = len(arr) - 1
    mid = 0
    while start<= end:
        mid = (start+ end) // 2
        # If x is greater, search in right array
        if arr[mid] < x:
            start = mid + 1

        # If x is smaller, search in left array
        elif arr[mid] > x:
            end= mid - 1
        # if x is present at mid
        else:
            return mid
 

    # when we reach at the end of array, then the element was not present
    return -1
 

arr = [ ]
n=int(input("Enter size of array : "))
print("Enter array  elements : ")
for i in range(n):
    e=int(input())
    arr.append(e)
x = int(input("Enter element to search "))
ans = binary_search(arr, x)
if(ans==-1):
    print("Element not found")
else:
    print("Element found at ",ans)
```

{% content-ref url="/pages/enW2lSXXp3eJnMVAPOII" %}
[Array](/my-docs/pythonnotes/abstract-data-structures/untitled-1/array.md)
{% endcontent-ref %}

{% content-ref url="/pages/WvqmSzLeimHHeTzSVLwo" %}
[Binary Search Tree](/my-docs/pythonnotes/abstract-data-structures/untitled-1/binary-search-tree.md)
{% endcontent-ref %}

{% content-ref url="/pages/elNgqdtjORrnmaofkEgI" %}
[Linked List](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-4.md)
{% endcontent-ref %}

{% content-ref url="/pages/vgEVzHJattVXgB9JCcXO" %}
[Extra-Array](/my-docs/pythonnotes/abstract-data-structures/untitled-1/array/extra-array.md)
{% endcontent-ref %}

{% content-ref url="/pages/7eiX2YnAhvNnjY7OiRJy" %}
[Stack](/my-docs/pythonnotes/abstract-data-structures/untitled-1/stack.md)
{% endcontent-ref %}

{% content-ref url="/pages/K2Fb2qoBZc5fio9pP5ZI" %}
[Binary Tree](/my-docs/pythonnotes/abstract-data-structures/untitled-1/binary-tree.md)
{% endcontent-ref %}

{% content-ref url="/pages/5w44kr7eSNwzBPsybKTo" %}
[Recursion](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-6.md)
{% endcontent-ref %}

{% content-ref url="/pages/4w3lLbf7UKIMgQ0GuYjN" %}
[Hash Table](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-5.md)
{% endcontent-ref %}

{% content-ref url="/pages/BLnvGjl0WoqZ9npdIr6P" %}
[Searching](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-2.md)
{% endcontent-ref %}

{% content-ref url="/pages/aDu8lYDCInQiGtYNEfzQ" %}
[Sorting](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-3.md)
{% endcontent-ref %}

{% content-ref url="/pages/nemaGQmas79yIx2pLK7y" %}
[Queue Sandbox](/my-docs/pythonnotes/abstract-data-structures/untitled-1/queue/queue-sandbox.md)
{% endcontent-ref %}

{% content-ref url="/pages/4w3lLbf7UKIMgQ0GuYjN" %}
[Hash Table](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-5.md)
{% endcontent-ref %}

{% content-ref url="/pages/Bw6QkD4iYM6zszBi6Pvs" %}
[Double Linked List](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-4/double-linked-list.md)
{% endcontent-ref %}

{% content-ref url="/pages/WKSCy91DvXLWkyMYSwoP" %}
[Graphs](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-1.md)
{% endcontent-ref %}

{% content-ref url="/pages/HA6U4P21mzp0ei2zS5qt" %}
[Exotic](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled.md)
{% endcontent-ref %}

{% content-ref url="/pages/bS4bA0QClN1EyxgFa7pw" %}
[Heap](/my-docs/pythonnotes/abstract-data-structures/untitled-1/heap.md)
{% endcontent-ref %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/binary-search.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.