prehistoricpenguin

Latency Comparison Numbers

Type	time	ms	comment
L1 cache reference	0.5 ns
Branch mispredict	5 ns
L2 cache reference	7 ns		14x L1 cache
Mutex lock/unlock	25 ns
Main memory reference	300 ns		20x L2 cache, 200x L1 cache

prehistoricpenguin

int 
binary_search_first_position(int *A, int n, int target) {
	int end[2] = { -1, n };
	while (end[0] + 1 < end[1]) {
		int mid = (end[0] + end[1]) / 2;
		int sign = (unsigned)(A[mid] - target) >> 31;
		end[1-sign] = mid;
	}
	int high = end[1];
	if (high >= n || A[high] != target)

prehistoricpenguin

/*
http://leetcode.com/onlinejudge#question_15
refer:http://en.wikipedia.org/wiki/3SUM
keyword :hash
*/
class Solution
{
public:
    vector<vector<int> > threeSum(vector<int> &num)
    {

prehistoricpenguin

/*
http://leetcode.com/onlinejudge#question_2
*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };