Searching for an element using Binary Search

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 searchlogarithmic 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.

Screenshot (50)

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.

screenshot-51-e1520200869702.png

 

 

 

 

 

 

Image Courtesy: Wikipedia

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Powered by WordPress.com.

Up ↑

%d bloggers like this: