Linear & Binary Search

Linear Search

---

Linear search is a sequential searching technique where we start from one end and check every element of the array until the desired element is found. It is the simplest searching. In this , we sequentially visit each element of an array until the target element is found thats why it is also called as Sequential Search

How linear Search works :

The following steps are followed to search for an element k = 1 in the array below.

(Step-1) : Start from the first element, compare k with each element

(Step-2) : If element == k, return the index

(Step-3) : Else, return not found.

Program :

Output :

Binary Search

---

It is a searching technique for finding an element's position in a sorted array. In this approach, the element is always searched in the middle portion of an array.

Binary search can be implemented only on a sorted array. If the elements are not sorted, we need to sort them first.

How Binary Search works :

The following steps are followed to search for an element k = 4 in the array below.

(Step-1) : Set two pointers low and high at the lowest and the highest positions respectively.

(Step-2) : Find the middle element (i.e. mid) of the array
⇛ arr[(low + high)/2] = 6

(Step-3) : If k == mid, then return mid. Else, compare the elements with the searched one.

(Step-4) : If k > mid, compare x with the elements on the right side of mid. This is done by setting low = mid + 1.

(Step-5) : Else, compare k with the elements on the left side of mid. This is done by setting high = mid - 1.

(Step-6) : Repeat steps 2 to 5 until low is equal to high.

(Step-7) : k = 4 is found.

Program :

Output :