Binary Search Algorithm

Binary search is a method used to find an item in a sorted list by repeatedly dividing the search interval in half. It's efficient and much faster than checking each item one by one, especially in large lists.

How does it works?

Imagine you have a sorted list of numbers from 1 to 100, and you want to find the number 73. Here’s how binary search would help:

• Start in the Middle: Look at the middle number in your list. In this case, it's 50.
• Compare: Is 73 greater than, less than, or equal to 50? Since 73 is greater, you know it must be in the upper half of the list.
• Narrow Down: Now, repeat the process with the upper half. The new middle is 75.
• Compare Again: Is 73 greater than, less than, or equal to 75? This time, 73 is less, so you focus on the numbers between 51 and 74.
• Repeat: Continue narrowing down by checking the middle number of the remaining section until you find 73.

Implementing binary search with TypeScript:

Why is Binary Search efficient?

Binary search has a time complexity of O(log n), making it much faster than a linear search, especially for large datasets.

Each time you compare, you cut the search space in half. This means if you have a list of 1000 items, you only need about 10 comparisons to find your item (because 2^10 is 1024).

• Sorted List: Binary search only works on sorted lists.
• Divide and Conquer: Always split the list into halves.
• Efficient: Reduces search time significantly compared to linear search.

Example and Explanation

Initial State:

• left = 0
• right = 9 (length of sortedArray - 1)

First Iteration:

• mid = Math.floor((0 + 9) / 2) = 4
• sortedArray[4] is 9, which is greater than 7
• Update right = mid - 1 = 3

Second Iteration:

• mid = Math.floor((0 + 3) / 2) = 1
• sortedArray[1] is 3, which is less than 7
• Update left = mid + 1 = 2

Third Iteration:

• mid = Math.floor((2 + 3) / 2) = 2
• sortedArray[2] is 5, which is less than 7
• Update left = mid + 1 = 3

Fourth Iteration:

• mid = Math.floor((3 + 3) / 2) = 3
• sortedArray[3] is 7, which equals the target
• Return 3

The target value 7 is found at index 3 in the array.

Practical Use Cases

E-commerce Platforms

Example: Amazon, eBay

• Product Search: When users search for products, the platform needs to quickly locate items in a vast inventory. Binary search can be used to efficiently find products in a sorted list of items by price, ratings, or relevance.

Database Management Systems

Example: Oracle, MySQL

• Indexing: Databases use indexing to speed up the retrieval of records. Binary search is used to traverse these indexes, which are often stored in sorted order, to quickly locate the desired data without scanning the entire database.

Social Media Platforms

Example: Facebook, LinkedIn

• Friend Search: Social media platforms use binary search to quickly find users or friends in a sorted list of names or user IDs, improving the efficiency of search functionalities.

Conclusion

Binary search is a highly efficient algorithm for finding elements in a sorted list, reducing search time to O(log n). By repeatedly dividing the search interval in half, it quickly narrows down the target location, making it a powerful tool for handling large datasets with minimal effort.