-
To search element 5 it will go step by step in 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
- On a sorted array or list, Binary Search is used. In binary search, we compare the value to the elements in the array's middle place.
- We return the value if the value is matched. If the value is less than or equal to the center element, it must be in the bottom half of the array; if it is more than or equal to the element, it must be in the upper half.
- On the bottom (or upper) half of the array, we repeat the procedure.
- When an array contains a huge number of elements, Binary Search comes in handy.
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);
- We compare the middle number of the list to the target in the previous programme logic, and if they match, we return. If it doesn't, we check to see if the middle value is larger or smaller than the target.
- If the Middle number is bigger than the Target, the binary search is restarted, but this time on the left half of the list, from the beginning to the middle, not beyond.
- If the Middle number is less than the Target, we repeat the binary search, but this time on the right half of the list, from the middle to the finish.
