Searching (Sequential and Binary search)

The process of locating required data is known as searching. Searching is the process of finding the location of the target among a list of objects.

A searching algorithm accepts two arguments as parameters—a target key value to be searched and the list to be searched. The search algorithm searches a target key value in the list until the target key is found or can conclude that it is not found.

Search techniques

The two basic search techniques are:

1. Sequential search

2. Binary search

i. Sequential Search

The easiest search technique is a sequential search. Sequential search begins with the first available record and proceeds to the next available record repeatedly until we find the target key or conclude that it is not found. Sequential search is also called as linear search.

Sequential search is suitable when the data is stored in an unordered manner and also when there is no way to directly access the data elements.

Algorithm:

1. Set i = 0, flag = 0

2. Compare key[i] and target

if(key[i] = target)

Set flag = 1, location = i and goto step 5

3. Move to next data element

i = i + 1

4. if(i < n) goto step 2

5. if(flag = 1) then

return i as position of target located

else

report as ‘Target not found’

6. stop

 

Consider the example

Index	0	1	2	3	4	5	6
Key	20	15	12	9	5	13	10

 

Let target data be 9.

Initially, i = 0 and the target element 9 is to be searched. At each pass, the target 9 is compared with the element at the i^th location till it is found or the index i exceeds the size.

The number of comparisons depends on where the target data is stored in the search list. If the target data is placed at the first location, we get it in just one comparison. Two comparisons are needed if the target data is in the second location. Similarly, i comparisons are required if the target data is at the i^th location and n comparisons, if it is at the nth location.

The average number of comparisons done by the sequential search method in the case of a successful search is (n + 1)/2.

An unsuccessful search is given by n comparisons. The number of comparisons is n and the complexity is denoted as O(n) which is worst case.

The best case complexity is 1, as the target data element is at the first location and requires only a single comparison.

Advantages

1. A simple and easy method

2. Efficient for small lists

3. Suitable for unsorted data

4. Suitable for storage structures which do not support direct access to data.

Disadvantages

1. Highly inefficient for large data.

ii. Binary Search

Binary search is the fast search algorithm with the time complexity of O(log n). It works on the principle of divide and conquer. This algorithm works on sorted data lists.

In binary search algorithm, to search for a particular element, it is first compared with the element at the middle position, and if it is found, the search is successful, else if the middle position value is greater than the target, the search will continue in the first half of the list; otherwise, the target will be searched in the second half of the list. The same process is repeated for one of the halves of the list till the list is reduced to size one.

Algorithm

1. Let n be size of the list

Let target be the element to be searched

Let flag = 0, low = 0, high = n-1

2. if low <= high, then

middle = (low + high)/2

   else goto step (5)

3. if(key[middle] = target)

Position = middle, fl ag = 1

Goto step (5)

   else if(key[middle] > target) then

high = middle − 1

   else

low = middle + 1

4. Goto step(2)

5. if flag = 1

report as target element found at location ‘position’

   else

report that element is not found in the list

6. stop

 

Consider the list

Index	0	1	2	3	4
Value	10	14	19	26	31

 

Let the target item be 26

compute mid= (low+high)/2

=(0+4)/2  = 2

So the mid of list is 2(index). It contains value 19. Compare 19 with target item 26. Since 19< 26

search is performed on right sublist.

 

Index	3	4
Value	26	31

 

Now low=mid+1   = 2+1  = 3

mid = (3+4)/2 =3

The data item in index 3 is 26 and it is equal to target data item. Search algorithm returns the index 3 and search is finished.

Advantages

1. Suitable for sorted data

2. Efficient for large lists

3. Suitable for storage structures that support direct access to data

4. Time complexity is O(log₂(n))

Disadvantages

1. Not applicable for unsorted data

2. Not suitable for storage structures that do not support direct access to data.

3. Inefficient for small lists