Jump to content

4.2.2.2 Binary Search

From Computer Science Knowledge Base

4.2.2.2 Binary Search

(Difficulty Note: This is slightly more complex than Linear Search, as it requires sorted data.)

Binary Search is a much faster way to find something, but it has a special rule: the list of items must be sorted (like numbers from smallest to largest, or words alphabetically). It works by repeatedly dividing the list in half.

How it works:

  1. Find the middle item in the sorted list.
  2. Is the middle item the one you're looking for?
    • If Yes, you found it! Stop.
    • If your item is smaller than the middle item, you know your item must be in the first half of the list. Get rid of the second half.
    • If your item is larger than the middle item, you know your item must be in the second half of the list. Get rid of the first half.
  3. Now you have a much smaller list. Repeat steps 1 and 2 with the new, smaller list until you find your item or the list becomes empty (meaning your item isn't there).

Example: Imagine finding a word in a dictionary. You don't start at 'A' and read every word. You open to the middle. If your word is earlier, you go to the middle of the first half, and so on.

Let's find 23 in the sorted list: [5, 9, 12, 16, 23, 30, 41, 50]

  • Middle is 16. 23 is larger than 16. New list: [23, 30, 41, 50]
  • Middle of new list is 30. 23 is smaller than 30. New list: [23]
  • Middle of new list is 23. (Yes!) – You found it!

Binary search is incredibly fast for large, sorted lists, like how search engines quickly find information in their vast sorted databases.

Bibliography:

Further Reading:

Retrieved from "https://wiki.omnivision.website/index.php?title=4.2.2.2_Binary_Search&oldid=432"