c/c++语言开发共享C基础 旋转数组查找题目

题目:      一类有序数组旋转查值问题.  例如:
　　有序数组 [ 1, 2, 3, 5, 5, 7, 7, 8, 9 ] 旋转后为 [ 5, 7, 7, 8, 9, 1, 2, 3, 5 ]  如何从中找出一个值索引, not found return -1.

//  // [1, 2, 3, 5, 5, 7, 7, 8, 9]  // 升序数组翻转后  // [5, 7, 7, 8, 9, 1, 2, 3, 5]  // 查找 value, return index, not found return -1;  //  int   search(int a[], int len, int v) {      int begin, end, mid;      // 异常判断      if (a == null || len <= 0)          return -1;        begin = 0;      end = len;      while (begin < end) {          mid = (begin + end) / 2;          if (a[mid] == v)              return mid;                    if (a[begin] < a[mid]) {              // 左边有序 [begin, mid]              if (a[begin] <= v && v < a[mid])                  end = mid;              else                  begin = mid + 1;          } else if (a[begin] > a[mid]) {              // 右边有序 [mid, end)              if (a[mid] < v && v <= a[end - 1])                  begin = mid + 1;              else                  end = mid;          } else {              ++begin;          }      }            // 没有找到      return -1;  }

// search_sort_state - 排序状态 -1 faild, 0 desc, 1 asc  static int search_sort_state(int a[], int len) {      int state, i, s[3];      if (a == null || len <= 0)          return -1;      // 默认 desc 降序      if (len == 1)          return 0;      // 1, 2 asc 升序, 但必须反转为 2, 1 变成降序. 因而当前降序 desc 原本就是升序 asc      if (len == 2)          return a[0] > a[1];            // 摘取不重复的3个内容      s[0] = a[0];        // 开始找 s[1]      for (i = 1; i < len; ++i) {          if (a[i] == s[0])              continue;          break;      }      // 所有值都一样, 走默认降序      if (i >= len)          return 0;        s[1] = a[i];      // 开始找 s[2]      while (i < len) {          if (a[i] == s[0] || a[i] == s[1]) {              ++i;              continue;          }          break;      }      // 只有两个不一样的值, 走默认降序      if (i >= len)          return s[0] > s[1];        s[2] = a[i];        state = 0;      state += s[0] > s[1] ? 1 : -1;      state += s[1] > s[2] ? 1 : -1;      state += s[2] > s[0] ? 1 : -1;      return state >= 0 ? 0 : 1;  }

// bsearch_asc - 二分查找升序查找  static int bsearch_asc(int a[], int begin, int end, int v) {      // 简单判断      if (begin >= end || v < a[begin] || v > a[end - 1])          return -1;        // 二分查找      do {          int mid = (begin + end) / 2;          int val = a[mid];            if (val == v)              return mid;            if (val < v)              begin = mid + 1;          else              end = mid;      } while (begin < end);        return -1;  }    static int search_asc(int a[], int len, int v) {      int begin = 0, end = len;      // 异常判断      if (begin >= end)          return -1;        while (begin < end) {          int mid = (begin + end) / 2;          if (a[mid] == v)              return mid;                    if (a[begin] < a[mid]) {              // 左边有序 [begin, mid]              if (a[begin] <= v && v < a[mid])                  return bsearch_asc(a, begin, mid, v);              // 右边无序, 继续循环              begin = mid + 1;          } else if (a[begin] > a[mid]) {              // 右边有序 [mid, end)              if (a[mid] < v && v <= a[end - 1])                  return bsearch_asc(a, mid + 1, end, v);              // 左边无须, 继续循环              end = mid;          } else {              ++begin;          }      }            // 没有找到      return -1;  }    // bsearch_desc - 二分查找降序查找  static int bsearch_desc(int a[], int begin, int end, int v) {      // 简单判断      if (begin >= end || v > a[begin] || v < a[end - 1])          return -1;        // 二分查找      do {          int mid = (begin + end) / 2;          int val = a[mid];            if (val == v)              return mid;            if (val > v)              begin = mid + 1;          else              end = mid;      } while (begin < end);        return -1;  }    static int search_desc(int a[], int len, int v) {      int begin = 0, end = len;        while (begin < end) {          int mid = (begin + end) / 2;          if (a[mid] == v)              return mid;                    if (a[begin] > a[mid]) {              // 左边有序 [begin, mid]              if (a[begin] >= v && v > a[mid])                  return bsearch_desc(a, begin, mid, v);              // 右边无序, 继续循环              begin = mid + 1;          } else if (a[begin] < a[mid]) {              // 右边有序 [mid, end)              if (a[mid] > v && v >= a[end - 1])                  return bsearch_desc(a, mid + 1, end, v);              // 左边无须, 继续循环              end = mid;          } else {              ++begin;          }      }            // 没有找到      return -1;  }
  //   // 题目:  //     一类有序数组旋转查值问题.  // 例如:  //     有序数组 [ 1, 2, 3, 5, 5, 7, 7, 8, 9 ] 旋转后为 [ 5, 7, 7, 8, 9, 1, 2, 3, 5 ]  // 如何从中找出一个值索引, not found return -1.  int   search_upgrade(int a[], int len, int v) {      int state, i, s[3];      if (a == null || len <= 0)          return -1;      // 默认 desc 降序      if (len == 1) {          if (a[0] == v)              return 0;          return -1;      }        if (len == 2) {          if (a[0] == v)              return 0;          if (a[1] == v)              return 1;          return -1;      }        // 摘取不重复的3个内容      s[0] = a[0];        // 开始找 s[1]      for (i = 1; i < len; ++i) {          if (a[i] == s[0])              continue;          break;      }      // 所有值都一样, 走默认降序      if (i >= len) {          if (s[0] == v)              return 0;          return -1;      }        s[1] = a[state = i];      // 开始找 s[2]      while (i < len) {          if (a[i] == s[0] || a[i] == s[1]) {              ++i;              continue;          }          break;      }      // 只有两个不一样的值, 走默认降序      if (i >= len) {          if (s[0] == v)              return 0;          if (s[1] == v)              return state;          return -1;      }        s[2] = a[i];      state = 0;      state += s[0] > s[1] ? 1 : -1;      state += s[1] > s[2] ? 1 : -1;      state += s[2] > s[0] ? 1 : -1;        // desc 降序, 旋转      if (state >= 0)          return search_desc(a, len, v);       // asc 升序, 旋转      return search_asc(a, len, v);  }

#include <stdio.h>  #include <stdlib.h>    #define len(a) (sizeof(a)/sizeof(*a))    // print - 数据内容打印  #define int_br (15)  static void print(int a[], int len) {      int i = 0;       while (i < len) {          printf(" %d", a[i]);          if (!(++i % int_br))              putchar('n');      }      if (i % int_br)          putchar('n');  }    int search_upgrade(int a[], int len, int v);    // sort - 旋转查找  int main(int argc, char * argv[]) {      int i, v;      int a[] = { 5, 7, 7, 8, 9, 1, 2, 3, 5 };      print(a, len(a));      // 开始测试      v = 8;      i = search_upgrade(a, len(a), v);      printf("%d -> %dn", v, i);
      v = 5;      i = search_upgrade(a, len(a), v);      printf("%d -> %dn", v, i);        v = 6;      i = search_upgrade(a, len(a), v);      printf("%d -> %dn", v, i);        v = 7;      i = search_upgrade(a, len(a), v);      printf("%d -> %dn", v, i);        v = 4;      i = search_upgrade(a, len(a), v);      printf("%d -> %dn", v, i);        int b[] = { 7, 6, 5, 3, 3, 2, 1, 9, 9, 8, 8, 7, 7 };      print(b, len(b));      // 开始测试      v = 8;      i = search_upgrade(b, len(b), v);      printf("%d -> %dn", v, i);        v = 5;      i = search_upgrade(b, len(b), v);      printf("%d -> %dn", v, i);        v = 6;      i = search_upgrade(b, len(b), v);      printf("%d -> %dn", v, i);        v = 7;      i = search_upgrade(b, len(b), v);      printf("%d -> %dn", v, i);        v = 4;      i = search_upgrade(b, len(b), v);      printf("%d -> %dn", v, i);        return exit_success;  }

$ gcc -g -wall sort.c ; ./a.out   5 7 7 8 9 1 2 3 5  8 -> 3  5 -> 0  6 -> -1  7 -> 2  4 -> -1   7 6 5 3 3 2 1 9 9 8 8 7 7  8 -> 10  5 -> 2  6 -> 1  7 -> 0  4 -> -1