Searching Algorithms

Question 1

What is a Binary Search

Answer 1

• 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

Question 2

Describe the pseudocode for a Binary Search

Answer 2

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

}

Question 3

What is the Time Complexity of a Binary Search

Answer 3

O (log n)

Question 4

What is a Linear Search

Answer 4

The process of going along data one by one until you find the desired result

Question 5

Describe the pseudocode for a Linear Search looking at a string Array (while loop)

Answer 5

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

Question 6

Describe the pseudocode for a Linear Search looking at a String array (for loop)

Answer 6

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

Question 7

What is the Time Complexity of a Linear Search

Answer 7

O (n)