Searching Algorithms

The simplest search method involves looping through the array X, checking for the required element. When it's found, the loop ends. This is not always the most efficient method (if the element is near the end of the array, it can take some time to find), but this is still an ok option when your array contains elements of different types and/or is not ordered.

Note that if an array contains multiple instances of an element, the process ends when the first instance (from left to right) is found.

Try It

JavaScript Code

// Search the array T for the element x, and return the index of the element if found:

function linearsearch( T, x ) {
	for ( i = 0; i < T.length; i++ ) {
		if (T[i] == x) { return i; break }
	}
}

This method is more efficient for sorted arrays (either numerical or alphabetical, though we'll stick with numerical for this sample). If you're looking for x in the array X, first find an element near the middle of the array. By comparing this center element to x, we can determine which half of the array x would be in. We then repeat this process on this half of the array only, each time reducing the size of the possible range where x could be.

Note that if an array contains multiple instances of an element, the process ends as soon as the new 'center' is equal to the searched for element - this may not be the occurrance with the lowest index. While this process is much

Try It

JavaScript Code

// Search the array T for the element x and return the index of x			 		

function binarysearch( T, x ) {
    var startIndex = 0;
    var endIndex = T.length - 1;
    var centerIndex = Math.floor((startIndex+endIndex)/2)

    var found = false
    while (T[centerIndex] != x && startIndex < endIndex) {
        if (x < T[centerIndex]) {			// if x less than center element, it must be in first half 
	        endIndex = centerIndex - 1		// change right end point
        }
        else if ( x > T[centerIndex]) { 	// if x greater than center element, it must be in second half
	        startIndex = centerIndex + 1	// change left end point
        }
        centerIndex = Math.floor((startIndex+endIndex)/2)	// recalculate center index with new end points
    }
 
	if ( T[centerIndex] == x ) { return centerIndex }	// if x is in the array, it'll be at new center index
}