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).
functioncould be written to implement binary search in Python. The array and search item can be passed as input variables to the
while loopthe middle element is computed first then checks
returnthe middle index
return-1 as the last statement in the
functionwith an array, search value, and
returnvalue from the
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  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
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
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