Searching and sorting

Lecture 23.

Searching: Linear and Binary
Finding a particular element in an array or some other kind of sequence. The element is called a key.

Linear Search
- timeconsuming

private int linearSearch (int key, int[] array){
   for (int i = 0; i < array.length; i++) {
      if (key == array[i]) return i;
   }
   return -1;
}

Binary search
Ask if the nr is higher/lower than the middle nr. Then ask again and again...
The idea of the binary search is the fact that area code array is an ascending order makes it possible to find a particular value much more efficiently. The key insight is that you get more information by starting at the middle element than you do by starting at the beginning.

private int binarySearch(int key){
   int kh = 0;
   int lh = display.length() -1;
      while ( lh <= rh){
         int mid = (lh+rh) / 2;
      if (key == disp.get(mid)) return mid;
      if (key < disp.get(mid)){
         rh = mid -1; //to move from the midpoint
}
   else{
      lh = mid +1;
}

Sorting
Selection sort and Radix sort algorithm
}
return -1;
}