Binary search<3

• Binary search algorithm


  1. More complex than linear search and requires all items to be in order

  2. With each loop, half of the data is removed from the search

  3. Uses the index of items in the list to determine the next item to be checked

  4. Identifies the midpoint by adding the lowest index to the highest index and dividing by two, then rounding to the nearest integer

  5. Starts by setting the counter to the middle position in the list

  6. If the value at the midpoint is a match, the search ends

  7. If the value at the midpoint is less than the value to be found, the search continues in the upper half of the list

  8. If the value at the midpoint is greater than the value to be found, the search continues in the lower half of the list
• Binary search


  • Requires all items to be in order
  • Removes half of the data with each loop
  • Uses the index of items in the list to determine the next item to be checked
  • Identifies the midpoint by adding the lowest index to the highest index and dividing by two, then rounding to the nearest integer
  • Starts by setting the counter to the middle position in the list
  • Ends the search if the value at the midpoint is a match
  • Continues the search in the upper half of the list if the value at the midpoint is less than the value to be found
  • Continues the search in the lower half of the list if the value at the midpoint is greater than the value to be found
• Loop


  The repetition of an activity within a computer program
• Data


  Units of information. In computing, there can be different data types, including integers, characters, and Boolean. Data is often acted on by instructions
• Index


  The position of a piece of data in a list. An index is the number given to the position of an item in a list
• Integer


  A whole number used to define numbers in a computer program. Integers can be unsigned (represent positive numbers) or signed (represent negative or positive numbers)
• Binary search


  If the value at the midpoint is less than the value to be found, the list is divided in half, the lower half of the list is ignored and the search keeps to the upper half of the list. If the value at the midpoint is greater than the value to be found, the upper half of the list is ignored and the search keeps to the lower half of the list. The search moves to the midpoint of the remaining items. Steps 2 through 4 continue until a match is made or there are no more items to be found.
• Binary search example


  • This algorithm could be used to search the following list for the number 7: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
• Trace table


  Used when testing a program to record changes in variable values as code executes
• Pseudocode


  A method of writing up a set of instructions for a computer program using plain English. This is a good way of planning a program before coding.