binarySearch<T>

A generic implementation of the Binary Search algorithm that efficiently finds a target element in a sorted list.

Function Signature

int binarySearch<T extends Comparable<T>>(List<T> list, T target)

Parameters

• list: A sorted list of elements of type T that implements the Comparable interface
• target: The element to search for in the list

Return Value

• Returns the index of the target element if found
• Returns -1 if the target element is not found in the list

Type Parameters

• T extends Comparable<T>: The type parameter T must implement the Comparable interface to ensure elements can be compared

Complexity Analysis

Time Complexity

• Best Case: O(1) - When the middle element is the target
• Average Case: O(log n)
• Worst Case: O(log n) - When the target is at either end or not present

Space Complexity

• O(1) - Only requires a constant amount of extra space

Implementation

int binarySearch<T extends Comparable<T>>(List<T> list, T target) {
  var left = 0;
  var right = list.length - 1;

  while (left <= right) {
    final mid = left + ((right - left) ~/ 2);
    final comparison = list[mid].compareTo(target);

    if (comparison == 0) {
      return mid;
    } else if (comparison < 0) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

Implementation Details

1. Function Declaration:

   • The function is generic, accepting any type T that implements Comparable<T>
   • Takes two parameters: the sorted list and the target element
   • Returns an integer representing the index of the target element

2. Algorithm Steps:

   • Maintains two pointers: left and right
   • Calculates the middle index
   • Compares the middle element with the target
   • Adjusts the search range based on the comparison
   • Continues until the element is found or the range is exhausted

Example Usage

void main() {
  // Searching in a list of integers
  var numbers = [11, 12, 22, 25, 34, 64, 90];
  var target = 25;
  print('List: $numbers');
  var index = binarySearch(numbers, target);
  print('Index of $target: $index');

  // Searching in a list of strings
  var fruits = ['apple', 'banana', 'grape', 'orange'];
  var searchFruit = 'grape';
  print('\nList: $fruits');
  var fruitIndex = binarySearch(fruits, searchFruit);
  print('Index of $searchFruit: $fruitIndex');
}

Output

List: [11, 12, 22, 25, 34, 64, 90]
Index of 25: 3

List: [apple, banana, grape, orange]
Index of grape: 2

Usage Notes

1. Prerequisites:

   • The input list MUST be sorted in ascending order
   • The type T must implement Comparable<T>
   • Built-in types like int, double, and String already implement Comparable

2. Performance Considerations:

   • Very efficient for large sorted datasets
   • Requires O(log n) comparisons in worst case
   • Consider using Linear Search for very small lists (n < 10)

3. Common Pitfalls:

   • Using with an unsorted list will give incorrect results
   • Not handling the -1 return value (element not found)
   • Using with a type that doesn't properly implement Comparable