RSS Feed
Twitter
August 17, 2017
CS Study
Before studying searching algorithms on array we should
know what is an algorithm?
An algorithm is a step-by-step procedure or method
for solving a problem by a computer in a given number of steps.
The steps of an
algorithm may include repetition depending upon the problem for which the
algorithm is being developed. The algorithm is written in human readable and
understandable form. To search an element in a given array, it can be done in
two ways: Linear search and Binary search.
Linear Search
A linear search is the basic and simple search algorithm.
A linear search searches an element or value from an array till the desired
element or value is not found and it searches in a sequence order. It compares
the element with all the other elements given in the list and if the element is
matched it returns the value index else it return -1. Linear Search is applied
on the unsorted or unordered list when there are fewer elements in a list.
Example with Implementation
To search the element 5 it will go step by step in a
sequence order.
function findIndex(values,
target)
{
for(var i = 0; i < values.length; ++i)
{
if (values[i] == target)
{
return i;
}
}
return -1;
}
//call the function
findIndex with array and number to be searched
findIndex([ 8 , 2 , 6 , 3 , 5
] , 5) ;
Binary Search
Binary Search is applied on the sorted array or list. In
binary search, we first compare the value with the elements in the middle position
of the array. If the value is matched, then we return the value. If the value
is less than the middle element, then it must lie in the lower half of the
array and if it's greater than the element then it must lie in the upper half
of the array. We repeat this procedure on the lower (or upper) half of the
array. Binary Search is useful when there are large numbers of elements in an
array.
Example with Implementation
To search an element 13 from the sorted array or list.
function findIndex(values,
target)
{
return binarySearch(values, target, 0,
values.length - 1);
};
function binarySearch(values,
target, start, end) {
if (start > end) { return -1; } //does
not exist
var middle = Math.floor((start + end) / 2);
var value = values[middle];
if (value > target) { return binarySearch(values,
target, start, middle-1); }
if (value < target) { return binarySearch(values,
target, middle+1, end); }
return middle; //found!
}
findIndex([2, 4, 7, 9, 13,
15], 13);
In the above program logic, we are first comparing the
middle number of the list, with the target, if it matches we return. If it
doesn't, we see whether the middle number is greater than or smaller than the
target.
If the Middle number is greater than the Target, we start
the binary search again, but this time on the left half of the list, that is
from the start of the list to the middle, not beyond that.
If the Middle number is smaller than the Target, we start
the binary search again, but on the right half of the list, that is from the
middle of the list to the end of the list.
Posted in 
0 Comments:
Post a Comment