Linear Search.
Linear search refers to traversing the array starting from the initial index to the end
Binary Search
The array must be sorted before we can do binary search. We then get the middle of the array and check whether it's equal to the element we are looking for. If it is not and it's bigger than the element then we need to only look in the right block of the array from the middle as the element couldn't possibly be in the left hand side. We keep making the block smaller and smaller till we find the element or return -1 to indicate that we couldn't find the element.
The binary search is more efficient than the linear search.
Let's say we have the below array:
1, 2 , 3 , 4, 7
0 1 2 3 4
We want to look for the element 7 . We keep 2 indexes called left and right and another variable mid.
left = 0
right = 4
mid = 2
We look at the mid element in the array and see that 7 is bigger than the middle element 2 so there's no way it could exist to the left hand side of the array. We update value of the left .
left = mid + 1 = 3
right = 4
mid = 3
We check the middle element at 3 which is 4 and 7 is greater than that so we update left again.
left = mid + 1 = 4
right = 4
mid = 4
We check the element at mid and find a match and the program ends .
File: "search.cpp"
#include <iostream>using namespace std;int linearSearch( int arr1[] , int size , int value ){ int result = -1 ; for( int i1=0 ; i1 < size ; i1++ ) { if ( arr1[ i1 ] == value ) return i1 ; } //for return -1 ;}int binarySearch( int arr1[] , int size , int value ){ if ( size == 0 ) return -1 ; int left = 0 ; int right = size - 1 ; int mid ; while ( left <= right ) { mid = ( left + right ) / 2 ; if ( arr1[mid] == value ) return mid ; else if ( arr1[mid] < value ) left = mid + 1 ; else right = mid - 1 ; } //while return -1 ;}int main(){ int arr1[] = { 4, 1 , 3 , 2, 7 } ; int arr2[] = { 1, 2 , 3 , 4, 7 } ; cout << linearSearch( arr1 , 5, 1 ) << endl ; cout << binarySearch( arr1 , 5, 7 ) << endl ; return 0;}