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).
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,while loop the middle element is computed first then checksreturn the middle indexreturn -1 as the last statement in the functionfunction with an array, search value, and print the results according to the return value from the functionNow, 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
