在一个已经排序的非降序整形数组中,找到被搜索整数首次出现的位置,如果该整数出现多次的话。要求在log2n次比交内完成。
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication3 { class Program { static void Main(string[] args) { int[] a = new int[] { 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 6, 7, 7, 7, 7, 7 }; for (int i = 1; i <= 7; ++i) { Console.WriteLine(string.Format("Search {0}, Index: {1}, TestResult: {2}", i, biSearch(a, i), biSearch(a, i) == sequenceSearch(a, i))); } } static int biSearch(int[] a, int t) { int n = a.Length; int l = 0; int b = n - 1; int f = -1; int m = -1; while (l <= b) { m = (l + b) / 2; if (a[m] < t) { l = m + 1; } else if (a[m] == t) { f = m; b = m - 1; } else //a[m] > t { b = m - 1; } } return f; } static int sequenceSearch(int[] a, int t) { for (int i = 0; i<a.Length; ++i) { if (t == a[i]) return i; } return -1; } } }
二分搜索首次出现被搜索元素的位置,布布扣,bubuko.com
原文:http://www.cnblogs.com/liquadli/p/3596192.html