Monday, September 29, 2014

Nine Chapter: Lesson 2 Binary Search and & Sorted Array


Lesson 2: Binary Search and Sorted Array

1. Binary Search and return the first index of the target number
13%
Accepted
Binary search is a famous question in algorithm.
For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity.
If the target number does not exist in the array, return -1.
Example
If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.

Understand the problem:
Note that the problem asks for finding the first index of the target number in O(logn) time. This is very different from classic binary search problem where you directly return the target number the first time you found it. 

Code (Java):
import java.util.Arrays;

class Solution {
    /**
     * @param array source array
     * @param target target to search
     * @return the first occurrence position of target
     */
    public int binarySearch(int[] array, int target) {
        
        if (array == null || array.length == 0) {
            return -1;
        }
        
        int lo = 0;
        int hi = array.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (array[mid] == target) {
                hi = mid;
            } else if (array[mid] > target) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        
        if (array[lo] == target) {
            return lo;
        }
        
        if (array[hi] == target) {
            return hi;
        }
        //write your code here
        return -1;
    }
}

Key Points:

  • start + 1 < end        // To prevent dead loop, e.g. 1, 2 and target = x caused the dead loop if we only checked 1 < 2
  • mid = lo + (hi - lo) / 2     // To prevent overflow
  • Line 11, hi = mid, to find its left part
  • A[start], A[end] == target? To check if the array has only three or less numbers and the target is in it. E.g. A = [1, 2, 3] and target = 1. The while loop while not execute. 

2. Binary Search and find the last index of the target number
This problem is quite simple. We only need to slightly modify the code above, change the line 21 as lo = mid, which means that we should go to the right half. At last, we checked the hi index first before the lo index.

Code (java):
import java.util.Arrays;

class Solution {
    /**
     * @param array source array
     * @param target target to search
     * @return the first occurrence position of target
     */
    public int binarySearch(int[] array, int target) {
        
        if (array == null || array.length == 0) {
            return -1;
        }
        
        int lo = 0;
        int hi = array.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (array[mid] == target) {
                lo = mid;
            } else if (array[mid] > target) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        
        if (array[hi] == target) {
            return hi;
        }
        
        if (array[lo] == target) {
            return lo;
        }
        //write your code here
        return -1;
    }

    public static void main(String[] args) {
      Solution sol = new Solution();
      int[] array = {1, 1, 1, 2, 2};
      int res = sol.binarySearch(array, 2);

      System.out.println(res);
    }
}

3. Search For a Range
Original post: http://buttercola.blogspot.com/2014/09/leetcode-search-for-range.html
public class Solution {
    public int[] searchRange(int[] A, int target) {
        if (A == null || A.length == 0) {
            int[] temp = new int[]{-1, -1};
            
            return temp;
        }
        
        // Search the starting position
        int start = searchStart(A, target);
        
        int end = searchEnd(A, target);
        
        int[] result = new int[2];
        result[0] = start;
        result[1] = end;
        
        return result;
    }
    
    private int searchStart(int[] A, int target) {
        int lo = 0;
        int hi = A.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (A[mid] == target) {
                hi = mid;
            } else if (A[mid] > target) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        
                
        if (A[lo] == target) {
            return lo;
        }
        
        if (A[hi] == target) {
            return hi;
        }
        
        return -1;
    }
    
    private int searchEnd(int[] A, int target) {
        int lo = 0;
        int hi = A.length - 1;
        
        while (lo + 1 < hi) {
            
            int mid = lo + (hi - lo) / 2;
            
            if (A[mid] == target) {
                lo = mid;
            } else if (A[mid] > target) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        
        if (A[hi] == target) {
            return hi;
        }
        
        if (A[lo] == target) {
            return lo;
        }
        
        return -1;
    }
}





4. Search Insert Postion














No comments:

Post a Comment