1 of 10

Searching Efficiency

Chapter 11.2 & 12.3

2 of 10

How to Search…

  • If you have an array of information or objects, how do you find a particular item in that array?

3 of 10

How to Search…

  • Linear Search
    • Develop a method that searches through the array, starting with the first item.
    • Looks at every item in that array until it finds what you’re looking for.

4 of 10

Linear Search

​

int search (String[] a, String searchValue) {

for (int i = 0; i < a.length; i++) {

if (a[i].equals(searchValue)) {

return i;

}

return -1;

}

​

5 of 10

Linear Search

  • Works very well with arrays of 100 or less pieces of information.
  • Speed gets worse when array is too large.

6 of 10

Binary Search

  • Examines the element at the array’s midpoint on each pass through the search loop.
  • If that element matches the target, it returns that position. If it is less than the target, it searches to the “right”. Otherwise, it searches to the “left”.
  • It adjusts the endpoints of the search in the array based on how the target sits in relation to the midpoint.

7 of 10

Binary Search

8 of 10

Binary Search

int search (int[] a, int searchValue) {

int left = 0;

int right = a.length – 1;

while (left <= right) {

int midpoint = (left + right) / 2;

if (a[midpoint] == searchValue) {

return midpoint;

} else if (a[midpoint] < searchValue) {

left = midpoint + 1;

} else {

right = midpoint – 1;

}

return -1;

}

9 of 10

Binary Search

  • It’s more efficient than a linear search because it never searches every item in the array.

​

10 of 10

Binary Search