Searching and Sorting


CodeBooks

This book will detail a variety of searching and sorting algorithms, for use and implementation.

Searching

Binary Search

Binary search is an algorithm commonly used to search through sorted arrays or lists. It works by bisecting the data, finding which half the target element is in, and bisecting that again, over and over. Here's an example:

I have a list containing all of the even numbers between 0 and 50, inclusive. I want to know what the index of 36 is.

  1.  The minimum index is 0, and the maximum is 25. The midpoint is (0 + 25) / 2 = 13. The middle value is item 13, or 26. 36 > 26, so we want the upper half of the data. 
  2.  The minimum index is 14, and the maximum is 25. The midpoint is (14 + 25) / 2 = 19. The middle value is item 19, or 38. 36 < 38, so we want the lower half of the data. 
  3.  The minimum index is 14, and the maximum is 18. The midpoint is (14 + 18) / 2 = 16. The middle value is item 16, or 32. 36 > 32, so we want the upper half of the data. 
  4.  The minimum index is 17, and the maximum is 18. The midpoint is (17 + 18) / 2 = 17. The middle value is item 17, or 34. 36 > 34, so we want the upper half of the data. 
  5.  The minimum index is 18, and the maximum is 18. The midpoint is (18 + 18) / 2 = 18. The middle value is item 18, or 36. 36 = 36, so we found our number. The index is 18. 

Here's an example code implementation.


        

Binary search doesn't have to hit every item in the array, so it gets more efficient the bigger the list is. If we take a list and count how many times binary search runs, then double the size of the list, the binary search will take only one more time to search the new array. This means it takes log-2 time to search an array. In Big-O notation, this is simplified to O(log n).

Sorting

//TODO this