February 9, 2023, Learn eTutorial

1084

Searching is the process of finding the occurrence of an element in a group. There are many techniques used for searching, Binary search is one of them. In a search, the algorithm tests for a match in the list and returns the index where matching is found, otherwise gives a message that the element is not found in the list.

The binary search algorithm is also called the "half interval algorithm" or "logarithmic algorithm". It works on a sorted array, If the given array is not sorted, the elements need to be sorted first, and then searching will be implemented on it. This algorithm works on a divide and conquers method. It will first divide the list into two by taking the middle element of the list and checking whether the search element matches with the middle element. If both are equal then returns the index otherwise, the algorithm chooses any one of the sublists where the chance is more the search element to be present. This division and search of sublists will continue until the size of the sublist reduces to zero.

It works faster on large lists than the smaller ones. The binary search tree and B-tree data structures are based on binary search. The repeated division of array in half reduces the time complexity of Binary search to O(logn).

- A
`function`

could be written to implement binary search in Python. The array and search item can be passed as input variables to the`function`

. and, - Using a
`while loop`

the middle element is computed first then checks - If the middle element is smaller than the search item then reset the left boundary to the index next to the middle element,
- else if the middle element is greater than the search item then reset the right boundary to the index just previous to the middle element,
- If the above conditions are not satisfied then the middle element will be the search item, So
`return`

the middle index - Repeat the above process until the size of sub-arrays reduces to zero.
- If the element doesn't exist then
`return`

-1 as the last statement in the`function`

- In the main section call the
`function`

with an array, search value, and`print`

the results according to the`return`

value from the`function`

Now, let's see the working of the Binary Search Algorithm. Take an array [ 12, 23, 26, 34, 38, 41 ] and search element 34. We have 12 at the start,41at the last, and 26 at the middle. Check if the middle one 26<34. It's true so the list to search becomes [34, 38, 41 ] i.e., the right subarray. Check if 38<34 it does not then check 38>34 it's true then now list becomes [34] and got a match, thus our search became successful.

**STEP 1**: Write a `function`

**binarySearch** with variables array **arr** and search value item.

**STEP 2**: Initialise variables **low** 0 and **high** last index

**STEP 3**: Start a `while loop`

to repeat until the condition **low**<=**high,**

**STEP 4**: Find the middle index of the array **mid **and check the middle element < **item** if matches then reset **low=mid**+1(right subarray)

**STEP 5**: else check if the middle element > **item** if matches then reset **high=mid**-1(left subarray)

**STEP 6**: else `return`

**mid** means match found

**STEP 6**: Now end the `function`

by `return`

-1 means no match found

**STEP 7**: Initialise an array **arr** with values and** item **to be searched

**STEP 8**: Call the **binarySearch()** with values **arr**, **item** and check the `return`

value and `print`

the suitable result

` ````
def binary_search(arr, item):
low = 0
high = len(arr) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
# If item is greater, ignore left half
if arr[mid] < item:
low = mid + 1
# If item is smaller, ignore right half
elif arr[mid] > item:
high = mid - 1
# means item is present at mid
else:
return mid
# If we reach here, then the element was not present
return -1
# Test array
arr = [ 12, 23, 26, 34, 38, 41 ]
item = 34
# Function call
result = binary_search(arr, item)
if result != -1:
print("Element is present at index", str(result))
else:
print("Element is not present in array")
```

Element is present at index 3