Searching Algorithms Flashcards
What is a Binary Search
- Can only be applied on sorted data
- Works by finding the middle element in a list of data before deciding which side of the data the desired element is to be found in
- The unwanted half of the data is then discarded and the process repeated until the desired element is found or until it is known that the desired element doesn’t exist in the data
Describe the pseudocode for a Binary Search
Function binarySearch (int[] data, int x) {
int Lower = 0
int upper = data.length -1
While (Lower <= Upper)
Mid = (Lower + Upper) DIV 2
If data[mid] == x
Return mid
Else if data[mid] < x
Lower = mid + 1
Else
Upper = Mid – 1
END IF
END WHILE
Return -1
END FUNCTION
}
What is the Time Complexity of a Binary Search
O (log n)
What is a Linear Search
The process of going along data one by one until you find the desired result
Describe the pseudocode for a Linear Search looking at a string Array (while loop)
Function LinearSearchString (String[] data, String x) {
count= 0
While count < data.length -1
If data[count] == x
Return count
Else
Count = count + 1
END IF
END WHILE
Return –1
END FUNCTION
Describe the pseudocode for a Linear Search looking at a String array (for loop)
Function LinearSearchString (String[] data, String x) {
For count = 0 to data.length - 1
If data[count] == x
Return count
Next Count
END IF
Return –1
END FUNCTION
What is the Time Complexity of a Linear Search
O (n)
