In this blog we will see how a particular element can be searched in a given list.
We will use a technique called Binary Search.
For Binary Search, the elements must be sorted.
According to Wikipedia,
In computer science binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with the remaining half being empty, the target is not in the array.
In the above code, we define a function called as binarysearch that accepts a list and the item to be searched. We define 2 variables first and last. First is the first element of the list and last is the last element of the list. We initialize a while loop that keep checking if the first element is less than or equal to the last element. i is defined as the middle element. The basic approach is
- If the middle element is the element that we are searching for, we return its position(i+1).
- If the middle element is greater than the element we are searching for , then last element becomes the element before the middle element. The element we are searching for is in the first half in this case.
- If the middle element is lesser than the element we are searching for , then first element becomes the element after the middle element. The element we are searching for is in the second half in this case.
We pass the list and the element we are searching for to the function called binarysearch. It returns the position of the element.
This will be the output.
Image Courtesy: Wikipedia