Searching

Searching

1. binary search

   • time comp.
     • O(log n), with base 2
   • overflow bug
     • its solution
       • mid= start + (end-start)/2
   • algorithm
   • condition
     • need sorted array
   • for strings
     • need lexicographically ordered array
       • a<b
       • ab<ac
       • a<aa
   • Ques- method to apply on unknown size sorted array

2. linear search

   • time comp.
     • O(n)
   • algorithm
   • improve linear search
     • transposition
     • move to front method

3. brute force searching

4. divide & conquer

   • problem into subproblems