Search yourself!

Hello geeks! It has been a long time since our last post, so here’s another very easy and interesting topic to enjoy, ‘Searching’!

Linear Search

Linear search also called as sequential search, is the simplest way to search an element from a given list. It is this search technique which you use almost everywhere in real life.

According to this concept, an item(key) is searched by comparing each given item with the key until it is either found, or the list of items is exhausted.

Algorithm

1.	Start
2.	Set i to 0
3.	 If i < number of elements in array
3.1	Check if array[i] equal to key
3.1.1	Print: element present in array at index (i+1)
3.2	Else
3.2.1	Set i to i+1
3.2.2	Go to step 3
4.	Else return -1
5.	End 

Explanation

In the beginning, a variable i is taken for iteration purpose and is set to 0.  Key is the element to be searched. Then the element at index ‘i’ is compared to key.n If the 2 are equal, then the index and the element can be printed. If not, the value of ‘i’ is iterated. The above statements are only executed when ‘i’ is less than the total number of elements in array.

Lets understand by example:-

• 

Uses

In real life, linear search can be used to search a word in the dictionary or find a book in the library. Also, linear search can be used to search an element in a given small list.

Time and space complexity

Worst-case-performance	O(N)
Best-case-performance	O(1)
Average-case-performance	O(N)
Worst-case-space complexity	O(1)

Advantages

1. Simple and easy to understand
2. Easy to implement
3. If the element to be searched is the first element, then you need not search the entire list!
4. Works on both sorted and unsorted arrays

Disadvantages

1. Not suitable for lists of large size

2. It is a slow searching algorithm

3.  If the element to be searched is the last element, then this searching technique becomes inefficient

Binary search

int Binary_search (array,s,e,x)       //function representation having integer return type
1.Start
2.Till e>s
     2.1 Declare mid = s + (e-s/2)
     2.2 Check if array[mid] equals x
           2.2.1 return mid 
    2.3 if(arr[mid] is less than x)
          2.3.1  s = mid +1
2.4 else e = mid - 1 
2.5 else return -1
3.End


** s stands for starting index, e stands for ending index, x is the value to be searched

Explanation

In this algorithm(above), we pass the following as parameters: the array, starting index, ending index,and the value to be searched(key). The function returns the index at which the key is present. As per the principle of binary search, the key value to be searched is compared with the middle element. Consequently, the array/list of elements is divided into 2 parts. 4 cases arise:-

1. The middle element is itself the key, hence value of index  is returned.

2. The key value is less than the middle element, we reduce our workspace from the whole array to the first half of the array. The element is searched for in the sub-array by using the loop in the function from ‘s’ till ‘e=mid-1’.

3. The key value is greater than the middle element , we reduce our workspace from the whole array to the second half of array. The element is searched for in the sub-array, by using the loop in the function from ‘s= mid+1’ till ‘e’.

4.The element does not exist in the array , ‘-1’ s returned, signifying that the element is not found in the array.

Lets understand by example:-

Time and space complexity

Worst-case-performance	O(log N)
Best-case-performance	O(1)
Average-case-performance	O(log N)
Worst-case-space complexity	O(1)

Time complexity

You must wondering how binary search’s complexity is O(log N). Lets determine this!!

Hence the searching is done with time complexity O(log N).

Use

It’s the most efficient search technique in terms of iterative approach.

Advantage

Its more efficient than linear search since , linear search takes, on average N/2 comparisons (where N is the number of elements in the array), and worst case N comparisons. Binary search takes an average and worst-case log 2 (N)comparisons. So for a million elements, linear search would take an average of 500,000 comparisons, whereas binary search would take 20.

Disadvantages

1.Its not as simple as linear search.

2.Its biggest disadvantage is that only list which is sorted can be allowed , it fails on unsorted list.

3.Also, binary search is not useful if the data structure we use does not allow random access. Eg. In case of array,its easy to jump to the middle element but , say in linked list , binary search may not be useful (may give wrong results).

Do try analyzing these algorithms and their time complexities, because practice makes perfect! and refer to our time complexity post for help

For any doubts or ambiguities, mail us at everythinggeeky.101@gmail.com, or comment below! 

Don’t forget to Like, Comment and Share with your friends.

Stay tuned for more interesting and geeky information, right here!

See you next week!

Cheers!

Team Bitxorbytes

Follow us on instagram:  @bitxorbytes

Image Credits: arcadiawindber.com/searching-for-something-to-do