Yorkville High School Computer Science Department
Yorkville High School Computer Science Department on Facebook  Yorkville High School Computer Science Department Twitter Feed  Yorkville High School Computer Science Department on Instagram

Yorkville High School Computer Science

ASSIGNMENTS: Hidden Figure - May 24, 2019

AP Computer Science :: Lessons :: Search Methods

Barron's AP Computer Science

Chapter 5:
Pages 271 - 272
Chapter 12
Pages 524 - 540


Fundamentals of Java
Chapter 11
Pages 411 - 415
Chapter 12
Pages 468 - 478

Searching

There are two main ways to search an array or list for a given value. A sequential search starts at the first element and compares it to a given value until that value is found or it reaches the end of an array. This search works better with an array that is already sorted. A binary search only works for a sorted array and uses a divide-and-conquer approach to work more efficiently. Binary search looks at an element in the middle of the array and, depending on the outcome, chooses the next half of the array to search. The code for each type of search in Java is below.

int seqSearch(int[] a, int value)
{
  for (int i=0; i<a.length; i++)
    if (a[i] == value)
      return i;
  return -1;
}
int binSearch(int[] a, int value, int left, int right)
{
  if (left > right)
    return -1;
  else
  {
    int midpoint = (left + right) / 2;
    if (a[midpoint] == value)
      return midpoint;
    else if (a[midpoint] < value)
      return binSearch(a, value, midpoint+1, right);
    else
      return binSearch(a, value, left, midpoint-1);
  }
}

Sequential searches have an average runtime of O(n) while binary searches have an average of O(log n). The following is a comparison of sequential search and binary search:

Sequential Search Binary Search
Sequential algorithm Divide-and-conquer algorithm
Works on any array Array MUST be sorted
Average Runtime: O(n) Average Runtime: O(log n)

 

Yorkville High School Computer Science Department on Facebook Yorkville High School Computer Science Department Twitter Feed Yorkville High School Computer Science Department on Instagram