28商机网创业项目/安卓优化大师官方版本下载

二分查找

二分查找代码

    二分查找的原理想必不用多解释了，不过有一点必须提醒读者的是，二分查找是针对的排好序的数组。OK，纸上读来终觉浅，觉知此事要躬行。我先来写一份，下面是我写的一份二分查找的实现（之前去某一家公司面试也曾被叫当场实现二分查找，不过结果可能跟你一样，当时就未能完整无误写出），有任何问题或错误，恳请不吝指正：

1. //二分查找V0.1实现版  

2. //copyright@2011 July  

3. //随时欢迎读者找bug，email：zhoulei0907@yahoo.cn。  

4.   

5. //首先要把握下面几个要点：  

6. //right=n-1 => while(left <= right) => right=middle-1;  

7. //right=n   => while(left <  right) => right=middle;  

8. //middle的计算不能写在while循环外，否则无法得到更新。  

9.   

10. int binary_search(int array[],int n,int value)  

11. {  

12.     int left=0;  

13.     int right=n-1;  

14.     //如果这里是int right = n 的话，那么下面有两处地方需要修改，以保证一一对应：  

15.     //1、下面循环的条件则是while(left < right)  

16.     //2、循环内当array[middle]>value 的时候，right = mid  

17.   

18.     while (left<=right)          //循环条件，适时而变  

19.     {  

20.         int middle=left + ((right-left)>>1);  //防止溢出，移位也更高效。同时，每次循环都需要更新。  

21.   

22.         if (array[middle]>value)  

23.         {  

24.             right =middle-1;   //right赋值，适时而变  

25.         }   

26.         else if(array[middle]<value)  

27.         {  

28.             left=middle+1;  

29.         }  

30.         else  

31.             return middle;    

32.         //可能会有读者认为刚开始时就要判断相等，但毕竟数组中不相等的情况更多  

33.         //如果每次循环都判断一下是否相等，将耗费时间  

34.     }  

35.     return -1;  

36. }  

出错率最高的在以下这么几个地方：

1. 注释里已经说得很明白了，可还是会有不少朋友犯此类的错误：

1.  //首先要把握下面几个要点：    

2.  //right=n-1 => while(left <= right) => right=middle-1;    

3.  //right=n   => while(left <  right) => right=middle;    

4.  //middle的计算不能写在while循环外，否则无法得到更新。    

2. 还有一个最最常犯的错误是@土豆：
   middle= (left+right)>>1; 这样的话left与right的值比较大的时候，其和可能溢出。

奇偶调序

题目：输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，
所有偶数位于数组的后半部分。要求时间复杂度为O(n)。

1. 维护两个指针，一个指针指向数组的第一个数字，向后移动；一个个指针指向最后一个数字，向前移动。如果第一个指针指向的数字是偶数而第二个指针指向的数字是奇数，我们就交换这两个数字。

    思路有了，接下来，写代码实现：

1.  //思路，很简答，俩指针，一首一尾  

2.  //如果第一个指针指向的数字是偶数而第二个指针指向的数字是奇数，  

3.  //我们就交换这两个数字  

4.    

5.  // 2 1 3 4 6 5 7   

6.  // 7 1 3 4 6 5 2  

7.  // 7 1 3 5 6 4 2  

8.    

9.  //如果限制空间复杂度为O（1），时间为O（N），且奇偶数之间相对顺序不变，就相当于正负数间顺序调整的那道题了。  

10.   

11. //copyright@2010 zhedahht。  

12. void Reorder(int *pData, unsigned int length, bool (*func)(int));  

13. bool isEven(int n);  

14. void ReorderOddEven(int *pData, unsigned int length)  

15. {  

16.     if(pData == NULL || length == 0)  

17.         return;  

18.       

19.     Reorder(pData, length, isEven);  

20. }  

21. void Reorder(int *pData, unsigned int length, bool (*func)(int))  

22. {  

23.     if(pData == NULL || length == 0)  

24.         return;  

25.     int *pBegin = pData;  

26.     int *pEnd = pData + length - 1;  

27.     while(pBegin < pEnd)  

28.     {  

29.         // if *pBegin does not satisfy func, move forward  

30.         if(!func(*pBegin))   //偶数  

31.         {  

32.             pBegin ++;  

33.             continue;  

34.         }  

35.           

36.         // if *pEnd does not satisfy func, move backward  

37.         if(func(*pEnd))      //奇数  

38.         {  

39.             pEnd --;  

40.             continue;  

41.         }  

42.         // if *pBegin satisfy func while *pEnd does not,  

43.         // swap these integers  

44.         int temp = *pBegin;  

45.         *pBegin = *pEnd;  

46.         *pEnd = temp;  

47.     }  

48. }  

49. bool isEven(int n)  

50. {  

51.     return (n & 1) == 0;  

52. }  

第一个只出现一次的字符

题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。

    分析：这道题是2006 年google 的一道笔试题。它在今年又出现了，不过换了一种形式。即最近的搜狐笔试大题：数组非常长，如何找到第一个只出现一次的数字，说明算法复杂度。此问题已经在程序员编程艺术系列第二章中有所阐述，在此不再作过多讲解。

代码，可编写如下：

1.  #include <iostream>  

2.  using namespace std;  

3.    

4.  //查找第一个只出现一次的字符，第1个程序  

5.  //copyright@ Sorehead && July  

6.  //July、updated，2011.04.24.  

7.  char find_first_unique_char(char *str)  

8.  {  

9.      int data[256];  

10.     char *p;  

11.       

12.     if (str == NULL)  

13.         return '\0';  

14.       

15.     memset(data, 0, sizeof(data));    //数组元素先全部初始化为0  

16.     p = str;  

17.     while (*p != '\0')  

18.         data[(unsigned char)*p++]++;  //遍历字符串，在相应位置++，（同时，下标强制转换）  

19.       

20.     while (*str != '\0')  

21.     {  

22.         if (data[(unsigned char)*str] == 1)  //最后，输出那个第一个只出现次数为1的字符  

23.             return *str;  

24.           

25.         str++;  

26.     }  

27.       

28.     return '\0';  

29. }  

30.   

31. int main()  

32. {  

33.     char *str = "afaccde";  

34.     cout << find_first_unique_char(str) << endl;  

35.     return 0;  

36. }  

  当然，代码也可以这么写（测试正确）： 

1.  //查找第一个只出现一次的字符，第2个程序  

2.  //copyright@ yansha  

3.  //July、updated，2011.04.24.  

4.  char FirstNotRepeatChar(char* pString)  

5.  {  

6.      if(!pString)  

7.          return '\0';  

8.        

9.      const int tableSize = 256;  

10.     int hashTable[tableSize] = {0}; //存入数组，并初始化为0  

11.       

12.     char* pHashKey = pString;  

13.     while(*(pHashKey) != '\0')  

14.         hashTable[*(pHashKey++)]++;  

15.       

16.     while(*pString != '\0')  

17.     {  

18.         if(hashTable[*pString] == 1)  

19.             return *pString;  

20.           

21.         pString++;  

22.     }  

23.     return '\0';  //没有找到满足条件的字符，退出  

24. }  

例子：

a a f b

hash[a]=2

hash[f]=1

hash[b]=1

注意：查询hash表的顺序aafb

原链接：http://blog.csdn.net/v_JULY_v/article/details/6460494