Exercises

Searching

Sequential/Linear

• iterates over elements in a list one by one until the target element is found

• keys are successively examined, starting from the first element until the last until a match is found

• inefficient for large inputs

• maximum number of searches required: n+1

• average number of searches required: (n+1)/2

  #include <iostream>
  
  using namespace std;
  
  int search(**const int* values,** int values_len, int value){
  	for(int i = 0; i < values_len; ++i) {
  		if (values[i] == value)
  			return i;
  	}
  	return -1;
  }
  
  int main() {
  	int **values[]** = {3, 2, 1, 0};
  	int **values_len = sizeof(values) / sizeof(int)**;
  	
  	cout << search(values, values_len, 2);
  	return 0;
  }
  

  def sequential_search(array, target):
      for i in range(len(array)):
          if array[i] == target:
              return i
      return -1
  

Binary

• searches a sorted list by repeatedly dividing the search interval in half

• more efficient, but requires a sorted list

• middle = left + (right - left)/2

• uses the “divide and conquer” technique

• begin with the element in the middle of the array as a search key,

  • if the value of the search key is equal to the item it returns the index of the search key,
  • otherwise if the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half (or left half)
  • otherwise, narrow it to the upper half (or right half)

  check repeatedly from the second point until the value is found or the interval is empty

  #include <iostream>
  
  using namespace std;
  
  int binary_search(**const** **int* values**, int values_len, int value){
  	int left = 0;
  	int right = values_len - 1;
  	
  	while (left <= right){
  		int middle = left + (right - left)/2;
  		
  		if (values[middle] == value){
  			return middle;
  		} else if (values[middle] < value){
  			left = middle + 1;
  		} else {
  			right = middle - 1;
  		}
  	}
  
  	return -1;
  }
  
  int main() {
  	int **values[]** = {0, 1, 2, 3};
  	int **values_len = sizeof(values) / sizeof(int)**;
  	
  	cout << binary_search(values, values_len, 2);
  	return 0;
  }
  

  def binary_search(arr, target):
      left, right = 0, len(arr) - 1
      while left <= right:
          mid = (left + right) // 2
          if arr[mid] == target:
              return mid
          elif arr[mid] < target:
              left = mid + 1
          else:
              right = mid - 1
      return -1
  

Merging

• combining two or more sorted arrays into one sorted array
• often used in merge sort, maintains sorted order
• we have 2 data sequences, sorted in increasing (or decreasing) order by the values of the keys
• in order to merge, a new sequence sorted in the same manner needs to be build from the 2 previous data sequences