Linear searching looks through a list\/array item by item until a target value is found, or the end of the list is reached. Linear searches can use unsorted lists, but are very inefficient.<\/p>\n
Binary searches only work on sorted lists, with the list repeatedly split into smaller and smaller lists, until the target value is found or the list is empty.<\/p>\n
Pointers are used to identify the range of the list to be sorted (low\/high, bottom\/top, left\/right, start\/end).\u00a0An index is chosen between the two pointers, resulting in a match or a value that is too high\/low. In the latter case the range pointers are updated, excluding the index that has just been checked.<\/p>\n
bottom = 0\ntop = listsize - 1\nfound = False\n \nloop while bottom<=top and found = False do\n middle = int( (top+bottom)\/2 ) #pick a midpoint\n if list[middle] = target then\n found = True #item found\n else if list[middle] > target then\n top = middle - 1 #look in bottom half\n else\n bottom = middle + 1 #look in top half\n end if\nend loop\n \nif found = True then \n print \"Found at index: \" + middle\nelse\n print \"Not found\"\nend if\n<\/pre>\n\r\n#set pointers to start and end of full list\r\nstart = 0\r\nend = len(array)\r\nfound = False\r\n\r\n# as long as pointers haven't crossed, and target has not been found\r\nwhile (start <= end) and not found:\r\n \r\n # pick the midpoint between pointers\r\n middle = (start + end) \/\/ 2\r\n \r\n # has target been found?\r\n if target == array[middle]:\r\n found = True\r\n # is target in lower half of range (start-middle)?\r\n elif target < array[middle]:\r\n end = middle - 1\r\n # target must be in upper half (middle-end)\r\n else:\r\n start = middle + 1\r\n \r\n# item has or has not been found \r\nif found:\r\n print "Found at index" , middle\r\nelse:\r\n print "Not found"\r\n<\/pre>\nPython functions terminate as soon as a value is returned. This can remove the need for a “found” variable:<\/p>\n
\r\ndef binary_search(array, target):\r\n start = 0\r\n end = len(array)\r\n\r\n while start <= end:\r\n middle = (start + end) \/\/ 2\r\n if target == array[middle]:\r\n return middle\r\n\r\n if target < array[middle]:\r\n end = middle - 1\r\n else:\r\n start = middle + 1\r\n\r\n return -1\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Linear searching looks through a list\/array item by item until a target value is found, or the end of the list is reached. Linear searches can use unsorted lists, but are very inefficient. Binary searches only work on sorted lists, with the list repeatedly split into smaller and smaller lists, until the target value is found or the list is empty. Pointers are used to identify the range of the<\/p>\n