Algorithm: Binary Search in Array

Binary search algorithm is enhancement in searching of element in array, It reduces worst case complexity of of linear search from O(n) to O(log₂n). In this algorithm all the elements in the array must be sorted.

BinarySearch(ArrayValues[], n, searchValue, LB, UB)

Here ArrayValues is an array of size n, Which is already sorted. In which we have to search an element searchValue. LB is lower bound and UB is an upper bound of the array. Mid is an intermediate variable which will contains middle element of array.

Algorithm: Linear Search For Array

In Linear Search algorithm whole array is traversed to search the element untill the element found.

Linear_Search(valArr[], n, searchValue)

Here valArr[] is of length n, and SearchValue  is a value which is to be found in the array. Consider lower bound of the array is 1. this algorithm will return index of first occurrence of the searchValue, and returns -1 on failure.

Step1: [Iterate the array]

           For index=1 to n repeat step 2 and 3

Step2:  if valArr[index]=searchValue then goto step 2(i) else goto step 3

                  i) return index

Step3: if index=n then goto step 3(i) else goto step 3(ii)

            i) return -1;

            ii) index=index-1;

Step4: End.

Algorithm: To remove element from Array

Algorithm: RemoveElementFromArray(rIndex,valArray[],n,removedData)

In this algorithm rIndex is index from which element is to be removed and n is the size of array valArray. removedData will contain the value which is removed from array from index rIndex.

*consider lower bound of array is 1.

Step 1: [Check for size of array]

           if rIndex > n then

                 a) raise_error "Array Index out of bound"
                 b) Exit
Step 2: removedData = valArray[rIndex]

Step 3: [Shifting elements of array]
           Declare index as integer
           i) for index=rIndex to n-1 repeat step a to b

               a) valArray[index] = valArray[index+1]
               b) index= index+ 1

           ii) valArray[index] = null

Step 4: End

Explanation

Algorithm: To insert element in array

Algorithm: InsertElementInArray(dataVal, valArray[], n, k,m)

In this algorithm dataVal is an element which is to be inserted in an array named valArray, whose size is n. we have to insert the element dataVal at index k. m is the total present elements in the array where m<n
*considering lower bound of array is 1.

Step 1: [Check for the size of array]
         if n < k then

                   a) RaiseError "Array Index out of bound"

                   b) goto step 5

Step 2: [Shifting the elements from k indexed elements by 1]

           i) for index = m  to k repeat step a to b

                 a) valArray[index+1] = valArray[index]
             
                 b) [Decrements counter]   index = index - 1

           ii) goto to step 3

Step 3: [Now Insert the element]

            valArray[k] = dataVal;

Step 4: Exit

Explanation

Arrays

Defination:

Array is a collection of homogeneous data elements with following properties

1. All the data elements are stored contiguous memory location
2. Data elements are accessed with index number.

There are 3 types of Array

• 1-D Array (Linear Array)
• 2-D Array (Matrix)
• N-D Array (Multidimensional Array)