Introduction To Searching

Searching is the process of checking and finding an element from a list of elements.

let's A be the collection of data elements i.e A is a linear array of say "n" elements. if we want to find the tresence of an element in "A", then we have to search for it. search is successful if data does appear in and unsuccessful otherwise.

There are several types of searching techniques one have some advantage(s) over other. Following are thr three important searching techniques:

1.Linear/sequential searching

2.Binary searching

3.Hashing

1.Linear Search

In linear search, each element of an collection is read one by one sequentially and it is compared with the desired element. A search is unsuccessful if all the elements are search and desired element is not found.

 

Algorithm for linear search

let say A be an array of "n" elements, "data" be the element to be searched. This algo will find data and display the location if all the elements are read and the desied element is present otherwise display data not found message.
1.read the array "A" of "n" elements and "data" to be searched and initialize flag=0
2.initialize i=0 and repeat through step 3 if i<n by incrementing "i" by 1
3.if (data==A[i])
    display data is found at location i
    flag=1
    return
4.if (flag=0)
  display "data is not found and search is unsuccessful"
5.exit

you can apply same algo for string,tuple,list and many more.

Time Complexity:

How time grow as input grow is called time complexity

i.Best case: O(1)  here size doesnot matter, whether size=1 or size=1000M, element found at oth index

ii.Worst case : O(N)

   here, N is the size of collection, here we donot find the target so have to check for every elements. so if 

  size=100       => 100 comparision

  size=1 lakh   => 1 lakh comparision

Space Complexity:

Are you taking some extra sapce is called space complexity.

example copy of array[],variable e.t.c

 

2.Binary Search

Binary search is an extremely efficient algo when it compared to linear search. Binary search technique searchs "data" in minimum possible comparisions. Suppose the given array is a sorted one, otherwise first we have to sort the array elements. then apply the following conditions to search a "data"

1.find the middle element of an array (n//2)

2.compare the middle elements with data to be searched, then there are following three cases

  i.if it is desired element , then search is successful

  ii.if it(middle element) is less than desired data, then search only the second half of the array, i.e elemnts which come to the right side of the middle element

  iii.if it is greater than desired data,then search only the first half of array. i.e elements which come to the left side of middle elements.

3.repeat same steps until an element is found or exhaust the search area.

 

Algorithm for binary search

1.Input an array and "data" to be search
2.lb=0,ub=len(array),find middle elements i.e mid=(lb+ub)//2  or mid=lb+(ub-lb)/2
3.repeat step 4 and 5 while (lb<=ub) and (array[mid]!=data)
4.if (data<array[mid])
    ub=mid-1
5.else
   lb=mid+1
6.mid=int((lb+ub)/2)
7.if array[mid]==data
  display "data found"
8.else
  display "data not found"
9.exit

Why binary search

Time complexity:

worst case: o(log(N)

 

3.Hashing

Hashing is the technique where we can compute the location of desired record in order to retrive it in a single access(or comparision).

Simply , Hashing is the process of mapping elements to indices in hash table using hash function. hashing is used in database indexing,password validation,cache memory management.

let's there is a table og "n" employee records and each employee record is defined bt aunique employee code , which is a key. if the key (or employee code ) is used as array index, then the recoed can be accessed by the key directly. if L is the memory location whrere each record is related with the key. if we can locate the memory address of the record from the key then desired record can be retrived in a single access.

hash function:

A function that transfer an element into array index is called hash function. it calculates index for each element in hash table based on its value.Aims to distribute elements evenly and minimize collisions.

if "h" is a hash function and "key" is the element , then h(key) is called as hash of key and is the index at which the element should be placed.

The basic idea of the hash function is the transformation of the key into the corresponding location in the hash table.

hash function "h" can be defined as a function that takes key as input and transfer it into a hash table index.

Some of common the hash functions are as follows:

1.Division method

h(x)=x mod m, where x is the element and m is size of the hash table

2.Midsquare method

h(x)=middle digits of x^2 , where x is the element 

3.Folding method

 h(x)=sum(parts of x), where the element is divided into parts and combined.

4.Multiplication Method

h(x)=fractional part of (kx), where k is a constant and x is the element

Hash table:

Data structure storing elements in array-like structure , with index calculated by hash function.

 

Collision:

suppose that two elements k1 and k2 are such that h(k1)=h(k2). then when element k1 is entered into the table , it is inserted at the position h(k1), but when k2 is hashed, an attempt may be made to insert the element into the same position where the element k1 is stored.

clearly, two elements can not occupy the same position. such a situation is known as hash collision or simply collision.

 

Collision resolution in hashing

Process of resolving conflicts when multiple elements are assigned the same hash value and mapped to the same index in a hash table.

Techniques:

1.Chaining

Linked list associated with each index in hash table.

2.Open addressing

find next available slot in hash table.

There are several mathods for finding the next available slot in open addressing including:

i.Linear probing

In this method , the algorithm checks the next index in a hash table until an empty slot is found. h(x,i)=(h'(x)+i) mod m, check next index

ii.Quadratic probing

In this method, the algo checks indices that are result of a quadratic function of the number of probes. h(x,i)=(h'(x)+cli+c2i^2) mod m , checks indices based on quadratic function of probes.

iii.Double hashing

In this method, the algo used two hash functions to find the next available slot. h(x,i)=(h1(x)+ih29x)) mod m ,uses two hash function

3.Rehashing

Resize hash table and rehash elements to new indices.